Floyd–Warshall (All-Pairs Shortest Paths)

The problem

Dijkstra’s algorithm finds shortest paths from one source. But sometimes you need the distance between every pair of places — think of the distance table printed in a road atlas. That’s the all-pairs shortest path problem.

Floyd–Warshall solves it with a beautifully short algorithm.

The idea: allow one more stop-over at a time

Number the vertices 1..V. Define:

dist[i][j] after round k = the shortest path from i to j that is allowed to pass only through vertices 1..k as stop-overs.

• Before any rounds, only direct edges are allowed (∞ if there is none).
• In round k, a path from i to j can either avoid k (keep the old value) or go through k:

dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

After the last round, every vertex is allowed as a stop-over, so dist holds the true shortest distances.

In the 3D model, the current stop-over k glows pink, the row and column of k (the values being used) are cyan, and each improved cell flashes yellow.

Walk-through

Take the cell B → D in the sample graph. With only direct edges it’s ∞ (there is no edge B → D).

• k = A: B → A → D = 8 + 7 = 15 → improved to 15.
• k = C: B → C → D = 2 + 1 = 3 → improved to 3.

Every other cell improves in the same way.

Code

INF = float('inf')

def floyd_warshall(dist):
    """dist: V x V matrix with 0 on the diagonal and INF for missing edges (modified in place)"""
    V = len(dist)
    for k in range(V):
        for i in range(V):
            for j in range(V):
                if dist[i][k] + dist[k][j] < dist[i][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]
    return dist

# The sample graph from the 3D model (A, B, C, D = 0..3)
d = [[0,   3,   INF, 7],
     [8,   0,   2,   INF],
     [5,   INF, 0,   1],
     [2,   INF, INF, 0]]
for row in floyd_warshall(d):
    print(row)
# [0, 3, 5, 6]
# [5, 0, 2, 3]
# [3, 6, 0, 1]
# [2, 5, 7, 0]

#include <iostream>
#include <vector>
using namespace std;
const int INF = 1e9;

int main() {
    vector<vector<int>> d = {{0, 3, INF, 7}, {8, 0, 2, INF}, {5, INF, 0, 1}, {2, INF, INF, 0}};
    int V = d.size();
    for (int k = 0; k < V; k++)
        for (int i = 0; i < V; i++)
            for (int j = 0; j < V; j++)
                if (d[i][k] < INF && d[k][j] < INF && d[i][k] + d[k][j] < d[i][j])
                    d[i][j] = d[i][k] + d[k][j];
    for (auto& row : d) { for (int x : row) cout << x << " "; cout << "\n"; }
}

The < INF checks in C++ stop INF + INF from overflowing.

Reconstructing the actual path

Keep a next[i][j] matrix: initially next[i][j] = j for every edge, and whenever you improve dist[i][j] through k, set next[i][j] = next[i][k]. Then follow next from i until you reach j.

Floyd–Warshall vs running Dijkstra V times

Detecting negative cycles

After the algorithm, if any dist[i][i] < 0, vertex i lies on a negative cycle — you could loop forever and keep getting “cheaper”, so shortest paths are undefined.

Common mistakes

• Putting the k loop inside instead of outermost — the results become wrong.
• Overflow when adding two “infinite” values.
• Forgetting dist[i][i] = 0 at the start.