C Program to Implement Floyd Warshall Algorithm

«

The Floyd-Warshall algorithm is a graph algorithm that finds the shortest path between two vertices in a graph in a weighted graph with positive or negative edge weights but without negative cycles. The algorithm is named after the British mathematician Floyd Warshall. The algorithm is also known as the all-pairs shortest path algorithm.

The algorithm compares all possible paths between two vertices in a graph and finds the shortest path. It does so in O(V3) time even when the graph is sparse.

In this algorithm, we will use a matrix to represent the graph. The matrix will have the following structure:

[
  [0, 1, 2, 3, 4],
  [1, 0, 5, 6, 7],
  [2, 5, 0, 8, 9],
  [3, 6, 8, 0, 10],
  [4, 7, 9, 10, 0]
]

Then, we will use the following formula to find the shortest path between two vertices:

d[i][j] = min(d[i][j], d[i][k] + d[k][j])

Example:
Fo example, if we have the following matrix:

advertisement
advertisement
\(\begin{bmatrix}
4 & 2 & 5 & 2\\
4 & 3 & 1 & 4\\
2 & 5 & 2 & 1\\
5 & 3 & 1 & 4
\end{bmatrix}\)

The shortest path matrix is:

\(\begin{bmatrix}
4 & 2 & 3 & 2\\
3 & 3 & 1 & 2\\
2 & 4 & 2 & 1\\
3 & 3 & 1 & 2
\end{bmatrix}\)

Problem Description

Write a C program that finds the shortest path between two vertices in a graph and prints the shortest path matrix using Floyd Warshall Algorithm.

Problem Solution

1. Ask the user to enter the edges of the graph as a matrix representation.
2. Print the original matrix.
3. Pass the matrix to the function floydWarshall to find the shortest path matrix.
4. Print the shortest path matrix.

Methods used:

  • void floydWarshall(int **, int) – This function will find the shortest path between two vertices in a graph using the Floyd-Warshall algorithm. The parameters are the graph represented as a matrix and the number of rows.
Program/Source Code

Here is the source code of a C Program that will find the shortest path between two vertices in a graph using the Floyd-Warshall algorithm. The C program is successfully compiled and run on a Linux system. The program output is also shown below.

  1. /*
  2.  * C Program to find the shortest path between two vertices in a graph
  3.  * using the Floyd-Warshall algorithm
  4.  */
  5.  
  6. #include <stdio.h>
  7. #include <stdlib.h>
  8.  
  9. void floydWarshall(int **graph, int n)
  10. {
  11.     int i, j, k;
  12.     for (k = 0; k < n; k++)
  13.     {
  14.         for (i = 0; i < n; i++)
  15.         {
  16.             for (j = 0; j < n; j++)
  17.             {
  18.                 if (graph[i][j] > graph[i][k] + graph[k][j])
  19.                     graph[i][j] = graph[i][k] + graph[k][j];
  20.             }
  21.         }
  22.     }
  23. }
  24.  
  25. int main(void)
  26. {
  27.     int n, i, j;
  28.     printf("Enter the number of vertices: ");
  29.     scanf("%d", &n);
  30.     int **graph = (int **)malloc((long unsigned) n * sizeof(int *));
  31.     for (i = 0; i < n; i++)
  32.     {
  33.         graph[i] = (int *)malloc((long unsigned) n * sizeof(int));
  34.     }
  35.     for (i = 0; i < n; i++)
  36.     {
  37.         for (j = 0; j < n; j++)
  38.         {
  39.             if (i == j)
  40.                 graph[i][j] = 0;
  41.             else
  42.                 graph[i][j] = 100;
  43.         }
  44.     }
  45.     printf("Enter the edges: \n");
  46.     for (i = 0; i < n; i++)
  47.     {
  48.         for (j = 0; j < n; j++)
  49.         {
  50.             printf("[%d][%d]: ", i, j);
  51.             scanf("%d", &graph[i][j]);
  52.         }
  53.     }
  54.     printf("The original graph is:\n");
  55.     for (i = 0; i < n; i++)
  56.     {
  57.         for (j = 0; j < n; j++)
  58.         {
  59.             printf("%d ", graph[i][j]);
  60.         }
  61.         printf("\n");
  62.     }
  63.     floydWarshall(graph, n);
  64.     printf("The shortest path matrix is:\n");
  65.     for (i = 0; i < n; i++)
  66.     {
  67.         for (j = 0; j < n; j++)
  68.         {
  69.             printf("%d ", graph[i][j]);
  70.         }
  71.         printf("\n");
  72.     }
  73.     return 0;
  74. }
Program Explanation

1. The program begins with asking the user to input the edges of the graph and represents them as a matrix representation.
2. Pass the matrix and the number of vertices n as input to the function floydWarshall.
3. In the function, loop nest from 0 to size and inside that make another loop from 0 to size where we compare the weights respectively as seen in the program.
4. Pass the matrix to the function floydWarshall to find the shortest path matrix.
5. Print the shortest path matrix.

Time complexity: O(V3)
The time complexity of the algorithm is O(V3), where V is the number of vertices in the graph.

advertisement

Space Complexity: O(V2)
The space complexity of the algorithm is O(V2), where V is the number of vertices in the graph.

Runtime Test Cases

In this case, we enter “4” as the number of vertices as input to find the shortest path between two vertices in the graph using the Floyd-Warshall algorithm.

Enter the number of vertices: 4
Enter the edges: 
[0][0]: 0
[0][1]: 12
[0][2]: 45
[0][3]: 2
[1][0]: 1
[1][1]: 0
[1][2]: 45
[1][3]: 32
[2][0]: 77
[2][1]: 43
[2][2]: 0
[2][3]: 2
[3][0]: 42
[3][1]: 3
[3][2]: 88
[3][3]: 0
The original graph is:
0 12 45 2 
1 0 45 32 
77 43 0 2 
42 3 88 0 
The shortest path matrix is:
0 5 45 2 
1 0 45 3 
6 5 0 2 
4 3 48 0
Additional Approach:

In this approach, we find the shortest distance between each pair of vertices in a given edge-weighted directed graph using the Floyd-Warshall algorithm.

Program/Source Code

Here is source code of the C Program to Implement Floyd-Warshall Algorithm. The C program is successfully compiled and run on a Linux system. The program output is also shown below.

advertisement
  1. // Program for Floyd Warshall Algorithm
  2. #include<stdio.h>
  3.  
  4. #define V 4 // Number of vertices in the graph
  5.  
  6. /* Define Infinite as a large enough value. This value will be used
  7.  for vertices not connected to each other */
  8. #define INF 99999
  9.  
  10. // A function to print the solution matrix
  11. void printSolution(int dist[][V]);
  12.  
  13. // Solves the all-pairs shortest path problem using Floyd Warshall algorithm
  14. void floydWarshell(int graph[][V])
  15. {
  16.     int dist[V][V], i, j, k;
  17.  
  18.     /* Initialize the solution matrix same as input graph matrix. Or
  19.      we can say the initial values of shortest distances are based
  20.      on shortest paths considering no intermediate vertex. */
  21.     for (i = 0; i < V; i++)
  22.         for (j = 0; j < V; j++)
  23.             dist[i][j] = graph[i][j];
  24.  
  25.     for (k = 0; k < V; k++)
  26.     {
  27.         // Pick all vertices as source one by one
  28.         for (i = 0; i < V; i++)
  29.         {
  30.             // Pick all vertices as destination for the
  31.             // above picked source
  32.             for (j = 0; j < V; j++)
  33.             {
  34.                 // If vertex k is on the shortest path from
  35.                 // i to j, then update the value of dist[i][j]
  36.                 if (dist[i][k] + dist[k][j] < dist[i][j])
  37.                     dist[i][j] = dist[i][k] + dist[k][j];
  38.             }
  39.         }
  40.     }
  41.  
  42.     // Print the shortest distance matrix
  43.     printSolution(dist);
  44. }
  45.  
  46. /* A utility function to print solution */
  47. void printSolution(int dist[][V])
  48. {
  49.     printf("Following matrix shows the shortest distances"
  50.         " between every pair of vertices \n");
  51.     int i, j;
  52.     for (i = 0; i < V; i++)
  53.     {
  54.         for (j = 0; j < V; j++)
  55.         {
  56.             if (dist[i][j] == INF)
  57.                 printf("%7s", "INF");
  58.             else
  59.                 printf("%7d", dist[i][j]);
  60.         }
  61.         printf("\n");
  62.     }
  63. }
  64.  
  65. // driver program to test above function
  66. int main()
  67. {
  68.     /* Let us create the following weighted graph
  69.     10
  70.     (0)------->(3)
  71.      |         /|\
  72.    5 |          |
  73.      |          | 1
  74.     \|/         |
  75.     (1)------->(2)
  76.      3           */
  77.     int graph[V][V] = { { 0, 5, INF, 10 },
  78.                         { INF, 0, 3, INF },
  79.                         { INF, INF, 0, 1 },
  80.                         { INF, INF, INF, 0 }
  81.                       };
  82.  
  83.     // Print the solution
  84.     floydWarshell(graph);
  85.     return 0;
  86. }
Program Explanation

1. Define number of vertices in the graph.
2. Define Infinite as a large enough value. This value will be used for the vertices that are not connected to each other.
3. dist[][] will be the output matrix that will finally have the shortest distance between every pair of vertices.
4. Initialize the solution matrix same as input graph matrix.
5. Add all vertices one by one to the set of intermediate vertices.
6. Before beginning an iteration, we have shortest distances between all pairs of vertices such that the shortest distances consider just the vertices in set {0, 1, 2,… k-1} as intermediate vertices.
7. After the end of a iteration, vertex no. k is added to the set of intermediate vertices and the set becomes {0, 1, 2, .. k}
8. Pick all vertices as source one by one and if vertex k is on the shortest path from i to j, then update the value of dist[i][j].
9. Print the shortest distance matrix.

Runtime Test Cases

Here is the result to find the shortest distance between each pair of vertices using Floyd-Warshall algorithm.

 
Following matrix shows the shortest distances between every pair of vertices 
      0      5      8      9
    INF      0      3      4
    INF    INF      0      1
    INF    INF    INF      0

To practice programs on every topic in C, please visit “Programming Examples in C”, “Data Structures in C” and “Algorithms in C”.

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & technical discussions at Telegram SanfoundryClasses.