Floyd-Warshall Algorithm
Floyd-Warshall is an all-pairs shortest path algorithm that finds shortest distances between every pair of vertices in a weighted graph. Unlike Dijkstra (single-source), it computes shortest paths from all vertices to all other vertices simultaneously. The algorithm can handle negative edge weights but not negative cycles. Developed independently by Robert Floyd, Bernard Roy, and Stephen Warshall in the early 1960s.
Visualization
Interactive visualization for Floyd-Warshall Algorithm
Floyd-Warshall Algorithm
Distance Matrix:
| 0 | 3 | ∞ | 7 |
| 8 | 0 | 2 | ∞ |
| 5 | ∞ | 0 | 1 |
| 2 | ∞ | ∞ | 0 |
• Time: O(V³)
• All-pairs shortest paths
• Works with negative edges (no negative cycles)
Interactive visualization with step-by-step execution
Implementation
1function floydWarshall(graph: number[][]): number[][] {
2 const n = graph.length;
3 const dist = graph.map(row => [...row]);
4
5 for (let k = 0; k < n; k++) {
6 for (let i = 0; i < n; i++) {
7 for (let j = 0; j < n; j++) {
8 if (dist[i][k] !== Infinity && dist[k][j] !== Infinity) {
9 dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]);
10 }
11 }
12 }
13 }
14
15 return dist;
16}Deep Dive
Theoretical Foundation
Floyd-Warshall uses dynamic programming with a 3D conceptual table. The key insight is to consider all vertices as potential intermediate vertices in a path. For each pair of vertices (i, j), the algorithm checks if going through an intermediate vertex k provides a shorter path than the current known path from i to j. The formula is: dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]). By considering vertices one by one as intermediate, it eventually finds the shortest path between all pairs. The algorithm runs in O(V³) time with three nested loops and uses O(V²) space for the distance matrix. It's based on the principle that the shortest path from i to j either goes through k or it doesn't.
Complexity
Time
O(V³)
O(V³)
O(V³)
Space
O(V²)
Applications
Industry Use
Network routing protocols (finding all shortest routes)
Computing road network distances between all city pairs
Transitive closure of directed graphs
Finding diameter of a graph (longest shortest path)
Detecting negative cycles in currency arbitrage
Game theory and optimization problems
Finding connected components in graphs
Computing betweenness centrality in social networks
Path analysis in electrical circuits
Use Cases
Related Algorithms
Depth-First Search (DFS)
Graph traversal exploring as deep as possible before backtracking. DFS is a fundamental algorithm that uses a stack (either implicitly through recursion or explicitly) to explore graph vertices. It's essential for cycle detection, topological sorting, and pathfinding problems.
Breadth-First Search (BFS)
Level-by-level graph traversal guaranteeing shortest paths in unweighted graphs. BFS uses a queue to explore vertices level by level, making it optimal for finding shortest paths and solving problems that require exploring nearest neighbors first.
Dijkstra's Algorithm
Finds shortest path from source to all vertices in weighted graph with non-negative edges. Uses greedy approach with priority queue.
Kruskal's Algorithm
Minimum Spanning Tree algorithm using greedy approach and Union-Find data structure. Sorts edges by weight and selects minimum weight edges that don't create cycles. Named after Joseph Kruskal, it's one of the most efficient MST algorithms for sparse graphs.