PATH-5 Floyd-Warshall · DSA

A timetable book lists the travel time between every pair of stations. Floyd–Warshall fills such a table in three nested loops, with negative weights allowed, and in about five lines of Python.

Every pair at once

The answer is a table d with V rows and V columns: d[i][j] is the distance from i to j. It has V² entries (V times V), so no method can do better than O(V²). Running a single-start method from every vertex is one way: V runs of Dijkstra cost O(V (V + E) log V), good for sparse graphs with no negative weights. Floyd–Warshall costs O(V³) (V · V · V) whatever the number of edges, works with negative weights, and works on the adjacency matrix of GRPH-1 directly.

Start the table from the edges: 0 on the diagonal, the weight of the cheapest edge from i to j, and ∞ where there is none.

Allowing one more station

Number the vertices 0 to V − 1. The middle vertices of a route are all its vertices except the first and the last. The method is a DP (DYNP-1) whose state is (i, j, k):

Before round 0 no middle vertices are allowed, so only single edges count: that is the starting table. In round k, vertex k is allowed too. The best route from i to j with middle vertices up to k either does not use k (then it is d[i][j] from before), or it uses k once: i → … → k → … → j, where both halves have middle vertices below k, so both are already in the table. (It never needs k twice: that would contain a cycle through k, which is not negative.) So the rule is

import math

def floyd_warshall(n, edges):
    d = [[math.inf] * n for _ in range(n)]
    for i in range(n):
        d[i][i] = 0
    for u, v, w in edges:
        d[u][v] = min(d[u][v], w)
    for k in range(n):
        for i in range(n):
            for j in range(n):
                if d[i][k] + d[k][j] < d[i][j]:
                    d[i][j] = d[i][k] + d[k][j]
    return d

Step through the figure. Each step shows one entry that changes, with the two entries it was made from outlined. Row B, column A gets its value 7 only in round D, from B → D (found in round C) and D → A.

FIG PATH-5.1Floyd–Warshall on a table

Loops

cost from row to column

06∞3

∞0−37

∞∞03

7∞∞0

1/9

Row i, column j holds the cheapest known cost from i to j. At first only direct lines count: 0 on the diagonal, ∞ where there is no line.

Step 1 of 9

A full table for every k would take V³ memory (V · V · V entries). The code keeps one table and changes it in place. That is safe, because in round k the entries d[i][k] and d[k][j] do not change: d[i][k] could only become d[i][k] + d[k][k], and d[k][k] is 0 (or less, if there is a negative cycle, which the next section deals with).

Why k is the outer loop

The rule reads d[i][k] and d[k][j], and they must already be the best values for “middle vertices below k”. With k outside, a whole round finishes before k moves on, so they are. Put k inside instead (for i, for j, for k) and each entry d[i][j] is worked out once, early, from entries that may still be ∞. Switch the figure to “k inside”: row B is filled while row C is still nearly empty, so B to A gets 14 instead of 7, and nothing ever comes back to fix it. The order of i and j does not matter; the order of k does.

Speed in Python

The three loops run V³ times: 3.4 million times for V = 150, about a second of plain Python. Building each new row with a list comprehension does the inner loop at C speed and is several times faster. Skipping rows where d[i][k] is ∞ saves more:

for k in range(n):
    dk = d[k]
    for i in range(n):
        dik = d[i][k]
        if dik != math.inf:
            d[i] = [min(a, dik + b)
                    for a, b in zip(d[i], dk)]

With NumPy, one whole round is one line: d = np.minimum(d, d[:, [k]] + d[k]).

Negative cycles, routes, and other uses

Negative cycles. A vertex i on a negative cycle ends with d[i][i] < 0: the cycle is a route from i to i that costs less than staying put. So after the loops, look at the diagonal. Then the table is not to be trusted for pairs whose routes can touch such a cycle. PATH-P5 needs this check.
Routes. Keep a second table nxt[i][j]: the first step from i towards j. Start it as j wherever there is an edge; whenever d[i][j] improves through k, set nxt[i][j] = nxt[i][k]. To list the route, follow nxt from i until j.
Reachability. With True and False instead of numbers, and “or” and “and” instead of min and +, the same loops give which vertex can reach which: the transitive closure (Warshall’s version). With each row stored as a Python int of bits (BITS-3), a whole row is one |.
Johnson’s method. For sparse graphs with negative weights: run Bellman–Ford once from a new vertex joined to every vertex with weight 0, giving each vertex a value h(v). Then every edge’s new weight w + h(u) − h(v) is 0 or more, and every route between the same two vertices changes by the same amount, h(i) − h(j), so shortest routes stay shortest. Now run Dijkstra from every vertex: O(V · E log V) in all. Lesson 7 uses the same kind of reweighting to explain A*.

Now try PATH-P5, Routes between asked pairs.

PATH-5 counts as completed once you step through the figure to the last step.

PATH-P5Practice: Routes between asked pairs PATH-6Shortest paths in DAGs