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

Ở đây chúng ta sẽ xem Thuật toán Johnson để tìm đường đi ngắn nhất giữa hai đỉnh.

Biểu đồ được đưa ra ở đây. Con đường ngắn nhất giữa các cạnh như dưới đây. Chương trình này sẽ lấy số lượng đỉnh, số cạnh và số cạnh với chi phí của chúng.

Đầu vào - Dọc:3

Các cạnh:5

Cạnh tranh 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 (chi phí)

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

Đầu ra - Ma trận để tìm đường đi ngắn nhất giữa bất kỳ đỉnh nào đến đỉnh bất kỳ.

Begin
   Create another matrix ‘A’ same as cost matrix, if there is no edge between ith row and jth column, put infinity at A[i,j].
   for k := 1 to n, do
      for i := 1 to n, do
         for j := 1 to n, do
            A[i, j] = minimum of A[i, j] and (A[i, k] + A[k, j])
         done
      done
   done
   display the current A matrix
End

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;
}
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++) { //take the input and store it into adj and cost matrix
      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; //if there is no edge, put infinity
      }
   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]); //find minimum path from i to j through 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";
   }
}

Đầu ra

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