Create Next App

Floyd-Warshall Algorithm

Resultant Distance Matrix

From / To	0	1	2	3
0	0	5	∞	10
1	∞	0	3	∞
2	∞	∞	0	1
3	∞	∞	∞	0

Floyd-Warshall - Technical Overview

1. Algorithm Description: The Floyd-Warshall algorithm computes shortest paths between all pairs of vertices, handling both positive and negative edge weights.

2. Steps of the Floyd-Warshall Algorithm:

Initialize a distance matrix using the input graph's adjacency matrix.
Iterate through every pair of vertices `(i, j)` and update their shortest path considering all other vertices `k` as intermediaries.

3. Time Complexity: O(V³) due to three nested loops over the vertices.

4. Space Complexity: O(V²) as a 2D matrix is required to store distances between all pairs.

5. Usage: Floyd-Warshall is used for finding shortest paths in dense graphs and can handle negative weights but not negative weight cycles.