Chương trình C++ triển khai thuật toán Johnson

Chúng ta sẽ xem thuật toán Johnson tìm đường đi ngắn nhất giữa hai đỉnh.

Đồ thị cho trước. Đường đi ngắn nhất giữa các cạnh như sau. Chương trình nhận số đỉnh, số cạnh, và các cạnh với chi phí.

Đầu vào - Đỉnh: 3

Cạnh: 5

Cạnh với chi phí:

1 2 8

2 1 12

1 3 22

3 1 6

2 3 4

Đầu ra - Ma trận khoảng cách của đồ thị.

Thuật toán

johnsonAlgorithm(cost)

Đầu vào - Ma trận chi phí của đồ thị cho trước.

Đầu ra - Ma trận đường đi ngắn nhất giữa mọi cặp đỉnh.

Bắt đầu
  Tạo ma trận 'A' giống ma trận chi phí, nếu không có cạnh giữa hàng i và cột j, đặt vô cực tại A[i,j].
  for k := 1 đến n, thực hiện
    for i := 1 đến n, thực hiện
      for j := 1 đến n, thực hiện
        A[i, j] = min của A[i, j] và (A[i, k] + A[k, j])
      done
    done
  done
  hiển thị ma trận A hiện tại
Kết thúc

Ví dụ

#include<iostream>
#define INF 9999
using namespace std;

int min(int a, int b);
int cost[10][10], adj[10][10];

inline int min(int a, int b){
  return (a < b) ? a : b;
}

int main() {
  int vert, edge, i, j, k, c;
  cout << "Enter no of vertices: ";
  cin >> vert;
  cout << "Enter no of edges: ";
  cin >> edge;
  cout << "Enter the EDGE Costs:\n";
  for (k = 1; k <= edge; k++) { // nhập và lưu vào ma trận adj và cost
    cin >> i >> j >> c;
    adj[i][j] = cost[i][j] = c;
  }
  for (i = 1; i <= vert; i++)
    for (j = 1; j <= vert; j++) {
      if (adj[i][j] == 0 && i != j)
        adj[i][j] = INF; // nếu không có cạnh, đặt vô cực
    }
  for (k = 1; k <= vert; k++)
    for (i = 1; i <= vert; i++)
      for (j = 1; j <= vert; j++)
        adj[i][j] = min(adj[i][j], adj[i][k] + adj[k][j]); // tìm đường đi nhỏ nhất từ i đến j qua k
  cout << "Resultant adj matrix\n";
  for (i = 1; i <= vert; i++) {
    for (j = 1; j <= vert; j++) {
      if (adj[i][j] != INF)
        cout << adj[i][j] << " ";
    }
    cout << "\n";
  }
  return 0;
}

Kết quả

Enter no of vertices: 3
Enter no of edges: 5
Enter the EDGE Costs:
1 2 8
2 1 12
1 3 22
3 1 6
2 3 4
Resultant adj matrix
0 8 12
10 0 4
6 14 0