Suppose a network needs the shortest distance between every pair of nodes, not just routes from one starting point. Floyd–Warshall solves this all-pairs shortest-path problem with dynamic programming. It builds a distance table once, then lets each pair’s answer be looked up directly. That differs from Dijkstra’s single-source approach, which would need to run again for each starting node. section 9.0 section 9.4
Start with a square matrix: each row is a starting node and each column is a destination. Then test possible detours.
- Put 0 on the diagonal, each direct edge’s weight in its cell, and infinity where no direct edge exists. section 9.1
- Choose a node k as a possible bridge. For every start i and destination j, keep the cheaper of the current distance and the route through k: dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]). section 9.1
- Repeat with every node as k. The bridge loop must surround the start and destination loops; the matrix can be updated in place. section 9.1 section 9.4
A shortcut appears
Imagine the current distance from node 4 to node 2 is infinity: no direct route is recorded. When node 1 becomes the bridge, the algorithm finds a route costing 2 + 2 = 4 and replaces infinity with 4. In the next phase, using node 2 as a bridge reveals a route from node 1 to node 4 costing 2 + 3 = 5. A phase need not change anything: testing node 3 finds no new shortcut in this example. section 9.1
Figure 9.2 Phase one of the algorithm (k=1). Node 1 is tested as an intermediate bridge for every pair of nodes. The algorithm discovers that routing a path from Node 4 to Node 2 via Node 1 costs 4 (2 + 2 = 4). Since 4 is less than the previous cost of infinity, a shorter route is found, and the matrix is overwritten in place to form A1
The first bridge phase shows why an indirect route can turn an infinite matrix entry into a finite distance. section 9.1
Three nested loops take O(V³) time whether the graph has few edges or many. The distance matrix takes O(V²) space, but afterward a distance lookup takes O(1) time. This trade-off suits dense graphs needing many pairwise answers; sparse graphs may be better served by repeated single-source searches. section 9.3 section 9.4
Negative edge weights are allowed, but a negative-weight cycle makes a shortest distance undefined: repeatedly circling it keeps lowering the cost. After the loops finish, check the diagonal. Any dist[i][i] below zero signals such a cycle. section 9.3
