All Pair Shortest Path: Floyd-Warshall Algorithm

The Floyd-Warshall Algorithm is a fundamental method employed to address the all-pairs shortest path issue, which calculates the shortest paths between every pair of vertices in a weighted graph, whether directed or undirected. The approach employs dynamic programming and is applicable to graphs that may include negative edge weights, provided there are no negative weight cycles.

 

The Floyd-Warshall method functions by progressively enhancing approximations of the shortest pathways through the use of intermediate vertices. The process begins by presuming that the direct edge between any two vertices represents the shortest way, subsequently refining the paths by evaluating all potential routes through intermediary vertices.

---

Steps of the Algorithm

Initialization

Create a 2D matrix dist[][] where each entry dist[i][j] initially holds the weight of the edge between vertices i and j. If no edge exists between i and j, set dist[i][j] = ∞ (infinity), except for dist[i][i] = 0 because the shortest path from a node to itself is zero. 

 

Iterative Update

The algorithm iterates through each vertex k (used as an intermediate vertex), and for each pair of vertices i and j, it checks whether using k as an intermediate vertex provides a shorter path from i to j. Mathematically: dist[i][j]=min⁡(dist[i][j],dist[i][k]+dist[k][j])

This step ensures that the shortest path from i to j is either the previously known shortest path or the path that goes through vertex k.

 

Final Output

After completing the updates, dist[i][j] will hold the shortest path from vertex i to vertex j. If there is no path between i and j, dist[i][j] will remain ∞.

---

Complexity Analysis

Time Complexity: The Floyd-Warshall algorithm has a time complexity of O(V^3), where V is the number of vertices in the graph. This is because of the three nested loops iterating over all vertices. 

 

Space Complexity: The space complexity is O(V^2) since the algorithm requires a 2D matrix to store distances between every pair of vertices.

Source code of Floyd-Warshall Algorithm

#include<stdio.h> #include<stdlib.h> #include<limits.h> void floyd_warshall(int ** adj_mat, int ** pred_mat, int n) { int i = 0, j = 0, k = 0; for (k = 0; k < n; k++) { for (i = 0; i < n; i++) { for (j = 0; j < n; j++) { if (adj_mat[i][j] > adj_mat[i][k] + adj_mat[k][j]) { adj_mat[i][j] = adj_mat[i][k] + adj_mat[k][j]; pred_mat[i][j] = k; } } } } } int main() { int **adj_mat, n, i = 0, j = 0, **pred_mat; scanf("%d", &n); adj_mat = (int ** ) malloc(n * sizeof(int * )); for (i = 0; i < n; i++) { adj_mat[i] = (int * ) malloc(n * sizeof(int)); } printf("Enter the distance value as %d if there does not exist any edge.\n", INT_MAX); for (i = 0; i < n; i++) { for (j = 0; j < n; j++) { scanf("%d", &adj_mat[i][j]); } } pred_mat = (int ** ) malloc(n * sizeof(int * )); for (i = 0; i < n; i++) { pred_mat[i] = (int * ) malloc(n * sizeof(int)); } for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (i != j || (adj_mat[i][j] != INT_MAX)) { pred_mat[i][j] = i; } else { pred_mat[i][j] = INT_MAX; } } } floyd_warshall(adj_mat, pred_mat, n); printf("Distance Matrix\n"); for (i = 0; i < n; i++) { for (j = 0; j < n; j++) { printf("%d ", adj_mat[i][j]); } printf("\n"); } printf("Predecessor Matrix\n"); for (i = 0; i < n; i++) { for (j = 0; j < n; j++) { printf("%d ", pred_mat[i][j]); } printf("\n"); } }

---

Happy Exploring!