Dynamic Programming II

The question

Five depots are joined by ten one-way roads. Each road has a cost, and two of them pay you to use them: a rebate of 3 on the road from depot 1 to depot 2, and a rebate of 2 on the road from depot 4 back to depot 0.

The dispatcher wants the cheapest cost from every depot to every other: 20 answers, one for each ordered pair. This is the all-pairs shortest paths problem (APSP): a directed graph on vertices $0,\dots ,n-1$ with integer edge weights, some negative, and for every pair the least weight $\delta (i,j)$ of a path from $i$ to $j$.

Negative roads are fine. A negative cycle is not: if a loop paid you to drive round it, "cheapest" would mean nothing. H has no such loop: the cycle $1\to 2\to 3\to 1$ costs $-3+2+2=1$, and no cycle costs less.

This module assumes Dynamic Programming I, which describes every dynamic program by seven decisions, and Dijkstra's and Bellman–Ford's single-source algorithms from a first algorithms course.

import itertools, math

INF = float("inf")
H = [(0, 1, 4), (0, 2, 9), (1, 2, -3), (1, 3, 7), (2, 3, 2), (3, 4, 3), (4, 0, -2),
     (2, 4, 8), (3, 1, 2), (4, 2, 6)]
W = {(u, v): w for u, v, w in H}

def weight(path):
    return sum(W[a, b] for a, b in zip(path, path[1:]))

def simple_paths(n, s, t):
    """Every path from s to t that repeats no vertex."""
    for size in range(n - 1):
        for middle in itertools.permutations([v for v in range(n) if v not in (s, t)], size):
            path = (s,) + middle + (t,)
            if all(edge in W for edge in zip(path, path[1:])):
                yield path

# No negative cycle: the cheapest simple cycle is 1 -> 2 -> 3 -> 1, of cost 1.
cycles = [weight(p) + W[p[-1], s] for s in range(5) for t in range(5)
          if t != s and (t, s) in W for p in simple_paths(5, s, t)]
assert min(cycles) == 1 == weight((1, 2, 3, 1))

DELTA = [[0 if s == t else min((weight(p) for p in simple_paths(5, s, t)), default=INF)
          for t in range(5)] for s in range(5)]
assert DELTA == [[0, 4, 1, 3, 6], [0, 0, -3, -1, 2], [3, 4, 0, 2, 5],
                 [1, 2, -1, 0, 3], [-2, 2, -1, 1, 0]]

From depot 0, depot 2 costs 1 (through depot 1 and its rebate), and from depot 1 you can get back to depot 0 for nothing. The table was found by trying every simple path: fine for five depots, hopeless for fifty.

The naive approaches, and where they waste work

Try every path. A complete graph has more than $(n-2)!$ simple paths between two vertices. That is exponential.

Run a single-source algorithm from every source. Dijkstra's algorithm is out: it settles a vertex for good once it is the closest unsettled one, and a negative road found later can undercut it. Bellman–Ford handles negative weights. It is itself a dynamic program: let $d_m(v)$ be the cheapest walk from the source to $v$ with at most $m$ edges. Then

$$d_m(v)=min(d_{m-1}(v),{min}_{(u,v)}{d}_{m-1}(u)+w(u,v)),$$

and with no negative cycle a cheapest path has at most $n-1$ edges, so $d_{n-1}=\delta$.

def bellman_ford(n, edges, s, count):
    d = [INF] * n
    d[s] = 0
    for m in range(1, n):                     # d holds d_{m-1}; build d_m
        nd = list(d)
        for u, v, w in edges:
            count[0] += 1                     # one relaxation
            if d[u] + w < nd[v]:
                nd[v] = d[u] + w
        d = nd
    return d

count = [0]
assert [bellman_ford(5, H, s, count) for s in range(5)] == DELTA
assert count[0] == 5 * 4 * 10 == 200

From every source that is $n·(n-1)·E$ relaxations: 200 here, and $\Theta (n^4)$ on a dense graph. The waste is easy to point at. The cheapest way from 1 to 3 (through 2, for $-1$) is rediscovered inside the run from 0, the run from 4, and the run from 1 itself. The five runs never share what they learn.

Choosing the state

A dynamic program needs a parameter that grows. Bellman–Ford's is the number of edges a path may use. Floyd and Warshall's idea (Roy 1959; Floyd and Warshall 1962) is which vertices a path may pass through.

Number the vertices $0,\dots ,n-1$. The intermediate vertices of a path are all of its vertices except the two ends. Then:

• State: $D_k[i][j]$ is the least weight of an $i\to j$ path whose intermediate vertices all lie in $\{0,\dots ,k-1\}$.
• Base case: $D_0$ allows no intermediates at all, so it is the road table: 0 on the diagonal, $w(i,j)$ for a road, $\infty$ otherwise.
• Answer location: $D_n[i][j]$, where every vertex is allowed.
• Recurrence: $$D_{k+1}[i][j]=min(D_k[i][j],D_k[i][k]+D_k[k][j]).$$

Proof of the recurrence. Take a cheapest $i\to j$ path $P$ whose intermediates lie in $\{0,\dots ,k\}$. With no negative cycle, cutting a cycle out never makes a path dearer, so $P$ can be taken simple: it visits $k$ at most once. If $P$ avoids $k$, it is one of the paths $D_k[i][j]$ ranges over. If $P$ passes through $k$, cut it there. The part $i\to k$ and the part $k\to j$ are paths whose intermediates lie in $\{0,\dots ,k-1\}$, so they cost at least $D_k[i][k]$ and $D_k[k][j]$. So $D_{k+1}[i][j]$ is at least the minimum on the right. It is also at most that minimum, because each term is the weight of a real walk that uses only allowed vertices, and a walk can be shortened to a path without getting dearer. By induction on $k$, the invariant holds after every round, and after round $n-1$ it says $D=\delta$.

The step not to skip is "visits $k$ at most once": that is where "no negative cycle" enters. With a negative cycle the loops still run, but they no longer compute path weights.

Floyd–Warshall on the depots

The road table, then one table per round; a shaded cell improved in that round.

Follow cell $(0,4)$. It is $\infty$ until round 2 allows $0\to 1\to 2\to 4$ (cost 9). Round 3 lowers it to 6, the path $0\to 1\to 2\to 3\to 4$, by adding two entries the table already had: $D[0][3]=3$ and $D[3][4]=3$. That is the saving over Bellman–Ford: the cheapest $0\to 3$ trip is computed once and reused by every pair that passes through 3.

The invariant can be tested: find by brute force the cheapest paths with intermediates in $\{0,\dots ,k\}$, and compare consecutive tables.

def restricted(n, k):
    """Brute force: cheapest paths whose intermediate vertices are all below k + 1."""
    return [[0 if s == t else min((weight(p) for p in simple_paths(n, s, t)
                                   if all(v <= k for v in p[1:-1])), default=INF)
             for t in range(n)] for s in range(n)]

tables = [restricted(5, k) for k in range(-1, 5)]    # k = -1: no intermediates, the road table
changes = [[(i, j, before[i][j], after[i][j]) for i in range(5) for j in range(5)
            if after[i][j] != before[i][j]] for before, after in zip(tables, tables[1:])]
assert [len(c) for c in changes] == [1, 5, 5, 4, 3]
assert changes[0] == [(4, 1, INF, 2)] and (0, 2, 9, 1) in changes[1]
assert (0, 4, INF, 9) in changes[2] and (0, 4, 9, 6) in changes[3]
assert changes[4] == [(1, 0, INF, 0), (2, 0, INF, 3), (3, 0, INF, 1)]
assert tables[-1] == DELTA

One table, filled in place

The recurrence names $n+1$ tables; the algorithm keeps one.

Evaluation order: $k$ outermost. Round $k$ reads only $D_k$ values, so the whole of round $k$ must finish before round $k+1$ starts. Inside a round, $i$ and $j$ may go in any order.

Space optimization: overwrite in place. In round $k$, a cell in row $k$ is offered $D[k][k]+D[k][j]=D[k][j]$, because $D[k][k]=0$. So row $k$ and column $k$ do not change during round $k$, and they are the only other cells the round reads. Overwriting early is therefore harmless, and $n^2$ numbers do the work of $n^3$.

Reconstruction. The dispatcher also wants routes. Keep a second matrix, nxt[i][j]: the vertex after $i$ on the best $i\to j$ path so far ($j$ itself for a road). When round $k$ improves $(i,j)$, the new path starts the way the best $i\to k$ path starts, so nxt[i][j] becomes nxt[i][k]. To read a path, follow nxt[·][j] from $i$ until you reach $j$. On H this gives $0\to 1\to 2\to 3\to 4$ for the pair $(0,4)$ and $1\to 2\to 3\to 4\to 0$ for $(1,0)$:

assert weight((0, 1, 2, 3, 4)) == DELTA[0][4] == 6
assert weight((1, 2, 3, 4, 0)) == DELTA[1][0] == 0

That completes the seven decisions:

Negative cycles show up on the diagonal

Run the same loops on a graph that has a negative cycle and they still finish. They just no longer compute path weights. Take three vertices with edges $0\to 1$ (cost 1), $1\to 2$ (cost $-2$) and $2\to 0$ (cost 0): the cycle costs $1-2+0=-1$.

Theorem. After Floyd–Warshall, some diagonal entry $D[i][i]$ is negative if and only if the graph has a negative cycle.

Sketch. Every entry the algorithm writes is the weight of a real walk, so a negative $D[i][i]$ is a negative closed walk, which contains a negative cycle. Conversely, take a negative cycle, its highest-numbered vertex $k$, and another vertex $i$ on it. The arc of the cycle from $i$ to $k$ and the arc from $k$ back to $i$ pass only through vertices below $k$, so just before round $k$ the table already holds values no larger than their weights, and round $k$ sets $D[i][i]$ to at most the cycle's weight, below 0. On the three-vertex example the diagonal ends negative. So the test is one line after the loops: if any $D[i][i]<0$, report the cycle instead of distances.

Two other programs for the same table

Bellman–Ford's state counts edges, and you can count edges for all pairs at once with the min-plus product:

$$(A\otimes B)[i][j]={min}_k(A[i][k]+B[k][j]),$$

matrix multiplication with $(min,+)$ in place of $(+,\times )$. If $D^{(m)}$ holds the cheapest walks of at most $m$ edges, then $D^{(2m)}=D^{(m)}\otimes D^{(m)}$: split a walk after its $m$-th edge. Squaring $\lceil {\log }_2(n-1)\rceil$ times reaches $n-1$ edges, and each product costs $n^3$ steps.

assert math.ceil(math.log2(5 - 1)) * 5**3 == 250

The three programs compute the same numbers and differ only in their state. Doubling the edge count takes $\log n$ full products. Adding one allowed vertex costs $n^2$, and $n$ of them finish the job. On H that is a factor of 2; at $n=1000$ it is $\lceil {\log }_{2}999\rceil =10$.

The cost of all pairs

Floyd–Warshall makes exactly $n^3$ relaxations: $n$ rounds of $n^2$ cells. That is $\Theta (n^3)$ time and $\Theta (n^2)$ space in the worst case, on a word-RAM where adding two weights costs $O(1)$. Reading a path out of nxt costs its length.

Is $n^3$ optimal? Nobody knows. Shaving factors smaller than any polynomial is possible (Williams, 2014, gets $n^3/2^{\Omega (\sqrt{\log n})}$), but for general weights no $O(n^{3-\epsilon })$ algorithm is known, for any fixed $\epsilon >0$, and a well-studied conjecture says none exists. Sparse graphs are different: with non-negative weights, Dijkstra from every source with a binary heap costs $O(nE\log n)$, which wins when $E$ is far below $n^2$. The vertex potentials of Minimum-Cost Flow remove negative weights without changing which paths are shortest, and open that route too.

Tours through every city

Now a different question, with the same kind of answer. A courier leaves city 0, must visit cities 1 to 5 once each, and must come back. The costs of the legs are symmetric:

This is the travelling salesperson problem (TSP). Brute force fixes city 0 first and tries the $(n-1)!=120$ orders of the rest. Going to the nearest unvisited city each time is fast, but here it builds $0,5,3,2,4,1$ for a cost of 60. The best tour costs 52.

T = [[0, 12, 19, 8, 23, 7], [12, 0, 9, 14, 17, 21], [19, 9, 0, 11, 7, 16],
     [8, 14, 11, 0, 13, 6], [23, 17, 7, 13, 0, 10], [7, 21, 16, 6, 10, 0]]

def tour_cost(tour):
    return sum(T[a][b] for a, b in zip(tour, tour[1:] + tour[:1]))

tours = [[0] + list(p) for p in itertools.permutations(range(1, 6))]
assert len(tours) == 120
assert min(map(tour_cost, tours)) == 52 == tour_cost([0, 1, 2, 4, 5, 3])

here, greedy = 0, [0]
while len(greedy) < 6:
    here = min((c for c in range(6) if c not in greedy), key=lambda c: T[here][c])
    greedy.append(here)
assert greedy == [0, 5, 3, 2, 4, 1] and tour_cost(greedy) == 60

Where does brute force waste work? Compare the tours that start $0,1,2,3$ with those that start $0,2,1,3$. Both prefixes have visited $\{1,2,3\}$ and stand at city 3, so every completion costs the same after either. Only the cheaper prefix can begin a best tour, yet brute force prices both families in full.

Held–Karp: the set, and where you stand

That observation is the whole algorithm (Bellman, and independently Held and Karp, 1962):

• State: $\mathrm{d}\mathrm{p}[S][j]$ is the cheapest path that starts at city 0, visits exactly the cities in $S\subseteq \{1,\dots ,n-1\}$ in some order, and ends at $j\in S$.
• Recurrence: the city before $j$ is some $k\in S⧵\{j\}$, and the path up to $k$ is itself a path from 0 through exactly $S⧵\{j\}$ that ends at $k$. So $$\mathrm{d}\mathrm{p}[S][j]={min}_{k\in S⧵\{j\}}(\mathrm{d}\mathrm{p}[S⧵\{j\}][k]+d(k,j)).$$
• Base case: $\mathrm{d}\mathrm{p}[\{j\}][j]=d(0,j)$.
• Evaluation order: increasing $S$ as a bitmask: every proper subset is a smaller number.
• Answer location: ${min}_j(\mathrm{d}\mathrm{p}[\{1..n-1\}][j]+d(j,0))$.
• Reconstruction: store each minimizing $k$; walk back from the best last city, removing it from $S$ at each step.
• Space optimization: two layers of values suffice, but then the stored $k$'s, and the tour, are gone.

Here is part of the table for the six cities: the sets inside $\{1,2,3\}$.

Column $\{1,2\}$ holds 28 (via 2, ending at 1) and 21 (via 1, ending at 2). The cell $\mathrm{d}\mathrm{p}[\{1,2,3\}][3]$ arrives at 3 from one of them: $28+14=42$ or $21+11=32$. It keeps 32 and remembers "came from 2". Checked by brute force:

def cheapest_path(S, j):
    """Brute force: the cheapest path 0 -> (all of S, in some order) ending at j."""
    return min(sum(T[a][b] for a, b in zip((0,) + p + (j,), p + (j,)))
               for p in itertools.permutations(sorted(set(S) - {j})))

assert [cheapest_path({1, 2}, j) for j in (1, 2)] == [28, 21]
assert cheapest_path({1, 2, 3}, 3) == min(28 + T[1][3], 21 + T[2][3]) == 32

Complexity: $n^2{2}^n$ against $n!$

One transition reads $\mathrm{d}\mathrm{p}[S⧵\{j\}][k]$ and adds $d(k,j)$. A set of size $s$ has $s$ choices of $j$ and $s-1$ choices of $k$, so the number of transitions is

$$\sum _{s=2}^{n-1}\left(\genfrac{}{}{0ex}{}{n-1}{s}\right)s(s-1)=(n-1)(n-2)2^{n-3}\le \frac{n^2{2}^n}{8}.$$

The table has $(n-1)2^{n-1}$ entries. So Held–Karp takes $O(n^2{2}^n)$ time and $O(n{2}^n)$ space in the worst case, on a word-RAM. Brute force has to price its tours, and a tour is $n$ additions. Even sharing prefixes (every partial order is priced once, from its parent), it makes one addition per partial order of the other $n-1$ cities plus one per closing leg: ${\sum }_{k=1}^{n-1}\frac{(n-1)!}{(n-1-k)!}+(n-1)!$, about $e·(n-1)!$. Held–Karp makes one addition per transition plus $n-1$ closing legs. For six cities that is 165 additions against 445, so the table already wins, and the gap only grows:

def transitions(n):
    return sum(math.comb(n - 1, s) * s * (s - 1) for s in range(2, n))

assert transitions(6) == 160
assert all(transitions(n) == (n - 1) * (n - 2) * 2 ** (n - 3) <= n * n * 2 ** n / 8
           for n in range(3, 25))
assert [transitions(n) for n in (8, 10, 12, 14)] == [1344, 9216, 56320, 319488]
assert math.factorial(13) == 6227020800

def brute_additions(n):                  # partial orders priced once each, plus closing legs
    return sum(math.perm(n - 1, k) for k in range(1, n)) + math.factorial(n - 1)

assert (transitions(6) + 5, brute_additions(6)) == (165, 445)
assert [brute_additions(n) for n in (8, 10, 12, 14)] == [18739, 1349289, 148421911, 23153818285]

It is still exponential: TSP is NP-hard, so no polynomial algorithm is expected, and the table alone has about 400 million entries at $n=25$. But within a billion additions, brute force handles 12 cities and Held–Karp handles 23.

assert 24 * 2**24 == 402_653_184                             # (n - 1) 2^(n - 1) entries, n = 25
assert brute_additions(12) < 10**9 < brute_additions(13)
assert transitions(23) + 22 < 10**9 < transitions(24)

A problem that looks different

A trader swaps between six currencies at posted rates: 1 unit of A buys 0.9 of B, 1 of B buys 1.2 of C, and so on for every pair. Can some sequence of trades start and end with A and make money? Nothing here mentions roads, yet one table from this lesson answers it once each rate is replaced by a different number. Which table, and which number? The lab's last problem is a different one.

Practise

In the lab you write Floyd–Warshall on a new graph and watch each round's table, every frame checked against a brute-force search. You predict a Held–Karp table layer by layer on five new cities, then write Held–Karp over bitmasks under an operation budget that trying every order cannot meet. You measure min-plus squaring against $n^3$, and finish with one problem that doesn't say what it is.

Recap

• You can now: compute all-pairs cheapest paths with negative edges and read the paths; detect a negative cycle from the diagonal; compare three dynamic programs for the same table by their state; and solve the travelling salesperson problem exactly for about 20 cities.
• Invariant: with no negative cycle, after round $k$, $D[i][j]$ is optimal over paths whose intermediates lie in $\{0,\dots ,k\}$; $\mathrm{d}\mathrm{p}[S][j]$ is optimal over paths from 0 through exactly $S$ to $j$.
• Complexity achieved: exactly $n^3$ relaxations for all pairs, against $n^3\log n$ by squaring and $n^{2}E$ by Bellman–Ford from every source; $(n-1)(n-2)2^{n-3}$ transitions for TSP, against about $e·(n-1)!$ additions for brute force. All worst case, on a word-RAM.
• Failure mode: the $k$ loop not outermost: the code runs, and some distances are wrong.
• In real software: SciPy's scipy.sparse.csgraph.floyd_warshall and NetworkX's floyd_warshall implement this algorithm; NetworkX's floyd_warshall_predecessor_and_distance also returns the predecessor matrix used to read paths.
• Next: Network Flow and Matchings turns to a different design tool, network flow: how much can get from $s$ to $t$, and the cut that proves no more can.

Check yourself

After the lab, the tutor will ask you to defend your work out loud:

1. State Floyd–Warshall's invariant, and prove that one round preserves it. Where exactly does "no negative cycle" enter the proof?
2. Add a road from depot 2 to depot 0 with cost $-4$ to H. What does the algorithm output, what should it report, and which pairs are affected?
3. For a dense graph on 1,000 vertices with some negative weights, compare Floyd–Warshall, min-plus squaring and Bellman–Ford from every source by their step counts.

Topic list modeled on the public schedule of CMU 15-451/651 Algorithm Design and Analysis (Fall 2025). All lecture text, proofs, examples, code, and exercises are original to SciMigo; no CMU course materials are reproduced. This course is independent and not affiliated with or endorsed by Carnegie Mellon University.