โปรแกรม C++ เพื่อใช้อัลกอริทึมของ Johnson

ที่นี่เราจะเห็นอัลกอริทึมของ Johnson เพื่อค้นหาเส้นทางที่สั้นที่สุดระหว่างจุดยอดสองจุด

กราฟได้รับที่นี่ เส้นทางที่สั้นที่สุดระหว่างขอบเป็นเหมือนด้านล่าง โปรแกรมนี้จะใช้จำนวนจุดยอด จำนวนขอบ และขอบด้วยต้นทุน

ป้อนข้อมูล − จุดยอด:3

ขอบ:5

ได้เปรียบด้วยต้นทุน -

1 2 8

2 1 12

1 3 22

3 1 6

2 3 4

ผลผลิต − เมทริกซ์ระยะทางของกราฟ

อัลกอริทึม

johnsonAlgorithm(ต้นทุน)

ป้อนข้อมูล − เมทริกซ์ต้นทุนของกราฟที่กำหนด

ผลผลิต − เมทริกซ์เป็นเส้นทางที่สั้นที่สุดระหว่างจุดยอดใดๆ ไปยังจุดยอดใดๆ

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

ตัวอย่าง

#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";
   }
}

ผลลัพธ์

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