Advertisement
Rakibul_Ahasan

Floyd–Warshall's Algorithm

Dec 23rd, 2019
159
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.49 KB | None | 0 0
  1. // C++ Program for Floyd Warshall Algorithm
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4. #define V 7
  5. #define E 12
  6. #define INF 99999
  7.  
  8. int graph[V][V];
  9.  
  10. void initial(){
  11.    
  12.     for (int i = 0; i < V; i++)
  13.     {
  14.         for (int j = 0; j < V; j++)
  15.         {
  16.             graph[i][j]=INF;
  17.         }
  18.     }
  19. }
  20.  
  21. void printSolution(int dist[][V])
  22. {
  23.     for (int i = 0; i < V; i++)
  24.     {
  25.         for (int j = 0; j < V; j++)
  26.         {
  27.             if (dist[i][j] == INF)
  28.                 cout<<"INF"<<"   ";
  29.             else
  30.                 cout<<dist[i][j]<<"  ";
  31.         }
  32.         cout<<endl;
  33.     }
  34. }
  35.  
  36. void floydWarshall (int graph[][V])
  37. {
  38.  
  39.     int dist[V][V], i, j, k;
  40.  
  41.     for (i = 0; i < V; i++)
  42.         for (j = 0; j < V; j++)
  43.             dist[i][j] = graph[i][j];
  44.  
  45.     for (k = 0; k < V; k++)
  46.     {
  47.         for (i = 0; i < V; i++)
  48.         {
  49.             for (j = 0; j < V; j++)
  50.             {
  51.                 if (dist[i][k] + dist[k][j] < dist[i][j])
  52.                 dist[i][j] = dist[i][k] + dist[k][j];
  53.                 //dist[i][j] = min(dist[i][j],dist[i][k] + dist[k][j]);
  54.  
  55.             }
  56.         }
  57.     }
  58.  
  59.     printSolution(dist);
  60. }
  61.  
  62. int main()
  63. {
  64.     initial();
  65.    // int graph[V][V];
  66. //    {   {0, 5, INF, 10},
  67. //        {INF, 0, 3, INF},
  68. //        {INF, INF, 0, 1},
  69. //        {INF, INF, INF, 0}
  70. //    };
  71.    
  72.      int u,v,w;
  73.       for(int i=0;i<E;i++){
  74.          cin>>u>>v>>w;
  75.          graph[u][v]=w;
  76.       }
  77.  
  78.  
  79.     floydWarshall(graph);
  80.     return 0;
  81. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement