Ardianta_Pargo

Floyd Warshall Algorithm

Oct 18th, 2014
326
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C 2.92 KB | None | 0 0
  1. #include<stdio.h>
  2. #include<assert.h>
  3. /* maxVertices represents maximum number of vertices that can be present in the graph. */
  4. #define maxVertices   100
  5. #define INF 123456789
  6. /* Input Format: Graph is directed and weighted. First two integers must be number of vertces and edges
  7.    which must be followed by pairs of vertices which has an edge between them.
  8.  */
  9. int min(int a,int b)
  10. {
  11.         return (a<b)?a:b;
  12. }
  13. void init(int distance[maxVertices][maxVertices])
  14. {
  15.         int iter,jter;
  16.         for(iter=0;iter<maxVertices;iter++)
  17.         {
  18.                 for(jter=0;jter<maxVertices;jter++)
  19.                 {
  20.                         if(iter==jter)
  21.                         {
  22.                                 distance[iter][jter] = 0;
  23.                         }
  24.                         else
  25.                         {
  26.                                 distance[iter][jter] = INF;
  27.                         }
  28.                 }
  29.         }
  30. }
  31. void FloydWarshall(int distance[maxVertices][maxVertices],int vertices)
  32. {
  33.         int from,to,via;
  34.         for(from=0;from<vertices;from++)
  35.         {
  36.                 for(to=0;to<vertices;to++)
  37.                 {
  38.                         for(via=0;via<vertices;via++)
  39.                         {
  40.                                 distance[from][to] = min(distance[from][to],
  41.                                                          distance[from][via]+distance[via][to]);
  42.                         }
  43.                 }
  44.         }
  45. }
  46. int main()
  47. {
  48.         int graph[maxVertices][maxVertices],size[maxVertices]={0},visited[maxVertices]={0};
  49.         int distance[maxVertices][maxVertices];
  50.         int vertices,edges,iter,jter;
  51.         /* vertices represent number of vertices and edges represent number of edges in the graph. */
  52.         scanf("%d%d",&vertices,&edges);
  53.         /*initialize distance between all pairs as infinity*/
  54.         init(distance);
  55.         int vertex1,vertex2,weight;
  56.         /* Here graph[i][j] represent the weight of edge joining i and j */
  57.         for(iter=0;iter<edges;iter++)
  58.         {
  59.                 scanf("%d%d%d",&vertex1,&vertex2,&weight);
  60.                 assert(vertex1>=0 && vertex1<vertices);
  61.                 assert(vertex2>=0 && vertex2<vertices);
  62.                 graph[vertex1][vertex2] = weight;
  63.                 distance[vertex1][vertex2] = weight;
  64.         }
  65.         FloydWarshall(distance,vertices);
  66.         for(iter=0;iter<vertices;iter++)
  67.         {
  68.                 for(jter=0;jter<vertices;jter++)
  69.                 {
  70.                         if(distance[iter][jter]>=INF)
  71.                         {
  72.                 printf("The shortest distance between %d and %d is Infinity\n",iter,jter);
  73.                         }
  74.                         else
  75.                         {
  76.                 printf("The shortest distance between %d and %d is %d\n",iter,jter,distance[iter][jter]);
  77.                         }
  78.                 }
  79.         }
  80.  
  81.         return 0;
  82. }
Advertisement
Add Comment
Please, Sign In to add comment