Floyd-Warshall Algorithm
The Floyd-Warshall algorithm finds the shortest paths between all pairs of nodes in a weighted graph, handling negative edge weights (but not negative cycles).
DIRECT EDGES
0
1
2
3
0
1
2
3
Start from the edges themselves: 0 on the diagonal, the edge weight where an edge exists, ∞ everywhere else.
Next
Could 1 reach 2 more cheaply via 0? ∞ + ∞ against 3.
Intuition
Imagine you have a map of cities. You want to know the shortest path between ANY two cities. Floyd-Warshall checks every possible "stopover" city (k) for every pair of cities (i, j). If going from i to j via k is faster than the current best way, it updates the map.
Concept
All-Pairs Shortest Path: Unlike Dijkstra (one-to-all), this computes the shortest path between every pair of vertices.
Dynamic Programming: It builds the solution incrementally by considering more intermediate nodes allowed in the path.
Relaxation Formula: dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
How it Works
The algorithm uses three nested loops:
- k (Intermediate): Iterate through each node as a potential pivot.
- i (Source): Iterate through each node as a starting point.
- j (Destination): Iterate through each node as a destination.
- Check if path
i -> k -> jis strictly improved. - Update the distance matrix if a shorter path is found.
Step-by-Step Breakdown
Watch the Matrix and Graph:
- Matrix Cell: Represents the current shortest distance between row (i) and column (j).
- Solid blue cell: dist[i][j], the distance being tested and, if the pivot helps, rewritten.
- Outlined cells: dist[i][k] and dist[k][j], the two distances whose sum is compared against it.
- Graph nodes: Solid blue is the pivot k, pale blue with a blue outline is i, and green is j.
- Blue edges: The two hops i to k and k to j that the comparison is made of.
When to Use
Applications:
- Finding optimal paths between all pairs of locations (e.g., flight routing).
- Transitive closure (determining reachability).
- Dense graphs where edge count is high.
When NOT to Use
- Large Graphs: O(V³) complexity makes it too slow for V > 400-500.
- Single-Source only needed: Use Dijkstra or Bellman-Ford if you only need paths from one specific start node.
How to Identify
"Find shortest paths between every pair of nodes", "Transitive closure", "Dense graph all-pairs".
Applying for software engineering roles? Free, no sign-up: