Introduction
i. Floyd-Warshall Algorithm finds shortest paths between all pairs of nodes.
ii. Works on weighted, directed or undirected graphs.
iii. Uses dynamic programming.
iv. No negative weight cycles allowed.
Key Points
Graph Type: Weighted, directed or undirected
Handles negative edge weights (no negative cycles)
Output: Matrix of shortest path distances
Algorithm Steps
i. Initialize distance matrix dist[][]
ii. For each intermediate vertex k = 0 to V-1
For each source vertex i = 0 to V-1
For each destination vertex j = 0 to V-1
Update: dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
Pseudocode
Example
Input: dist[][] = [[0, 4, 10⁸, 5, 10⁸],
[10⁸, 0, 1, 10⁸, 6],
[2, 10⁸, 0, 3, 10⁸],
[10⁸, 10⁸, 1, 0, 2],
[1, 10⁸, 10⁸, 4, 0]]
Output:[[0, 4, 5, 5, 7],
[3, 0, 1, 4, 6],
[2, 6, 0, 3, 5],
[3, 7, 1, 0, 2],
[1, 5, 5, 4, 0]]
Explanation:
Complexity
Time Complexity: O(V³)
Space Complexity: O(V²)
Best for dense graphs
Use Case
Used in network routing, map applications, transport systems
Calculates shortest distances between every location pair
All-pairs routing in networks
Flight and transportation systems