🎓 A1Learner
🔍

DSA Floyd–Warshall

Floyd–Warshall computes the shortest distance between every pair of vertices in one table. It grows the table by allowing one more intermediate vertex at a time.

Direct against via

No direct edge joins vertex 0 and vertex 2 here. The route through vertex 1 costs 8 and wins the cell.

INF = float("inf")
dist = [[0, 5, INF], [INF, 0, 3], [INF, INF, 0]]
print("direct 0 -> 2:", dist[0][2])
print("via 1:", dist[0][1] + dist[1][2])
dist[0][2] = min(dist[0][2], dist[0][1] + dist[1][2])
print("best 0 -> 2:", dist[0][2])

One stage of growth

Allowing vertex 1 as an intermediate rewrites exactly one cell. The route from 0 through 1 to 2 now costs 8.

INF = float("inf")


def show(dist):
    for row in dist:
        print(["inf" if v == INF else v for v in row])


dist = [[0, 5, INF, 10], [INF, 0, 3, INF],
        [INF, INF, 0, 1], [INF, INF, INF, 0]]
print("stage: no intermediate allowed")
show(dist)
k = 1
for i in range(4):
    for j in range(4):
        if dist[i][k] + dist[k][j] < dist[i][j]:
            dist[i][j] = dist[i][k] + dist[k][j]
print("stage: vertex 1 allowed")
show(dist)

Every stage in order

The stage loop runs on the outside of the other two loops. That order is what gives each stage its meaning.

INF = float("inf")
dist = [[0, 2, INF], [INF, 0, 2], [INF, INF, 0]]
for k in range(3):
    for i in range(3):
        for j in range(3):
            if dist[i][k] + dist[k][j] < dist[i][j]:
                dist[i][j] = dist[i][k] + dist[k][j]
                print("via", k, ":", i, "->", j, "now", dist[i][j])
print("final:", dist)

Example

INF = float("inf")


def show(dist):
    for row in dist:
        print(["inf" if v == INF else v for v in row])


n = 4
dist = [[INF] * n for _ in range(n)]
for i in range(n):
    dist[i][i] = 0
for u, v, w in [(0, 1, 5), (0, 3, 10), (1, 2, 3), (2, 3, 1)]:
    dist[u][v] = w
print("stage: direct edges only")
show(dist)
updates = 0
for k in range(n):
    for i in range(n):
        for j in range(n):
            if dist[i][k] + dist[k][j] < dist[i][j]:
                dist[i][j] = dist[i][k] + dist[k][j]
                updates += 1
    print("stage: intermediates up to", k)
    show(dist)
print("cell improvements:", updates)

Key points

  • An intermediate vertex is a vertex allowed to sit in the middle of a path.
  • Stage k allows only vertices numbered up to k as intermediates.
  • The update compares the stored distance with the route through vertex k.
  • The diagonal stays zero, because staying at one vertex costs nothing.
  • A missing edge starts as infinity and may shrink at a later stage.

In this example, the table starts with direct edges only and infinities elsewhere. Allowing vertex 1 fills the 0 to 2 cell with 8. Allowing vertex 2 improves two more cells, and allowing vertex 3 improves none. Three cell improvements in total produce the final all-pairs table.

Note

the table holds n squared cells, and the three nested loops try n cubed updates.

Try it Yourself

Edit the code, then press Run.

Running is simulated · Python Playground

Exercise

What does stage k allow that stage k minus 1 did not?