The all-pairs shortest path (APSP) problem asks for the minimum path cost between every pair of vertices in a weighted graph. Floyd–Warshall solves it in one run, building a global distance matrix rather than searching outward from one starting vertex at a time. section 9.0 section 9.4
For each possible intermediate vertex k, compare the known cost from i to j with the cost of going from i to k and then k to j. Keep the cheaper value; after testing every bridge, the matrix stores the shortest distance for every pair. Initialize direct edges with their weights, self-distances with zero, and missing connections with infinity. section 9.1 section 9.4
A bridge creates a shorter route
In the four-node walkthrough, testing node 1 as a bridge changes the distance from node 4 to node 2 from infinity to 4, using edges with costs 2 and 2. Later phases test the remaining nodes and complete the distance matrix. section 9.1
Figure 9.1 The initial state of the network. The left panel shows the directed, weighted graph. The right panel shows the baseline distance matrix (A0). Existing direct paths are recorded with their cost, while missing connections are initialized to infinity (∞). The diagonal is zero, as the distance from any node to itself is zero.
Use the initial graph and distance matrix to see how direct edges, unreachable pairs, and self-distances are represented before the updates begin. section 9.1
The method takes O(V³) time and O(V²) space, and can update its matrix in place. It trades upfront computation for constant-time distance lookups afterward. It supports negative edge weights and can detect a negative cycle when a final diagonal entry is negative; repeated single-source searches are more efficient on sparse graphs. section 9.1 section 9.4
