Dynamic Programming on Graphs

The Graphs module's Shortest Paths lesson introduced three algorithms (Dijkstra, Bellman–Ford, Floyd–Warshall) and remarked that one operation, relaxation, underlies them all. The Principles of Dynamic Programming lesson then distilled DP into optimal substructure plus overlapping subproblems. This lesson connects the two ideas with a single thesis: many graph algorithms are dynamic programs, and relaxation is the DP transition.

The pattern is always the same. We define a subproblem as the best value obtainable using a restricted resource, and we grow the resource one unit at a time. The resource is whatever we ration:

• the set of intermediate vertices a path may pass through (Floyd–Warshall);
• the number of edges a path may use (Bellman–Ford, $K$-stops);
• a topological prefix of an acyclic graph (DAG-DP);
• a subset of vertices already visited (Held–Karp, the Bitmask DP lesson).

Relaxing an edge $(u,v)$, testing whether routing through $u$ improves the current estimate for $v$, is exactly the $\min$ over choices in a DP recurrence. Once you see this, is there a path?, what is the cheapest path?, and how many shortest paths are there? all become the same exercise: pick the resource, write the recurrence, choose an evaluation order that respects the dependencies.¹

Floyd–Warshall: intermediate vertices as the resource

Number the vertices $1,\dots ,V$. Restrict which vertices a path is allowed to pass through internally, and relax that restriction one vertex at a time.

The base case $d_0[i][j]$ is $w(i,j)$ if the edge exists, $0$ if $i=j$, and $+\infty$ otherwise, since no intermediate vertices are allowed, so only direct edges count. The induction is the core of the method.

The lemma is a verbatim DP transition, route through $k$ or don't:

Because $d_k$ depends only on $d_{k-1}$, and the two cells it reads in row/column $k$ are unchanged when $i=k$ or $j=k$, we can drop the $k$ index and update the matrix in place. This yields the entire algorithm in three nested loops with $k$ outermost:

The triple loop is $\Theta (V^3)$ time and $\Theta (V^2)$ space, independent of the edge count, which is what makes Floyd–Warshall the method of choice for dense graphs where we want every pair at once.²

Path reconstruction uses a $\text{next}$ matrix (above) initialized to $\text{next}[i][j]=j$ for each edge: whenever routing through $k$ wins, the first hop out of $i$ toward $j$ becomes the first hop toward $k$. To rebuild a path, follow $i\to \text{next}[i][j]\to \cdots \to j$. (A $\text{pred}$ matrix storing the last vertex before $j$ is the symmetric alternative.) The practice problem Find the City With the Smallest Number of Neighbors at a Threshold Distance is Floyd–Warshall verbatim: compute all-pairs distances, then count for each city how many others lie within the threshold.

Bellman–Ford: edges as the resource

Floyd–Warshall rations intermediate vertices. Bellman–Ford rations edges, which makes it a single-source DP over path length.

A walk of at most $t$ edges to $v$ is either a walk of at most $t-1$ edges to $v$, or such a walk to some predecessor $u$ followed by the edge $(u,v)$:

Each round is one full sweep of edge relaxations, exactly the relaxation primitive from the Shortest Paths lesson, now indexed by a layer $t$. Because a shortest path in a graph with no negative cycle is simple, it uses at most $V-1$ edges, so $D_{V-1}$ is the answer: after $V-1$ rounds the table converges. If one more round still relaxes some edge, a path of $\ge V$ edges beats every shorter one, which can only happen along a negative cycle, so that extra relaxation is the standard negative-cycle test.³ The cost is $V-1$ sweeps of $E$ edges, $O(VE)$.

The layered view pays off directly when the problem caps the number of edges. Cheapest Flights Within K Stops asks for the cheapest $s\to t$ route using at most $K$ stops, i.e. at most $K+1$ edges. That is precisely $D_{K+1}[t]$: run exactly $K+1$ Bellman–Ford rounds, no more.

DAG-DP: a topological prefix as the resource

When the graph is acyclic, the resource becomes trivial to ration: process vertices in topological order. A topological order lists every vertex after all of its predecessors, so by the time we reach $v$, every $D[u]$ for an incoming edge $(u,v)$ is already final. The recurrence has no cycles, so a single pass suffices, with no convergence over $V-1$ rounds and no $\min$ over $k$ layers.

Each vertex and edge is touched once, so DAG-DP runs in $\Theta (V+E)$, faster than Dijkstra and immune to negative weights, because acyclicity replaces the non-negativity that Dijkstra needs. The longest path problem, NP-hard in general graphs, is just as easy on a DAG: swap $\min$ for $\max$. Acyclicity is what makes the difference.⁴

In the figure, $d$ is reached by $3+4=7$ via $b$ versus $2+1=3$ via $c$; the $\max$ keeps the through-$b$ edge (in acc), and because $b$ and $c$ were finalized before $d$ in topological order, one forward sweep settles it.

Counting paths rides on the same order. To count all paths $s\to t$ in a DAG, set $\text{cnt}[s]=1$ and accumulate $\text{cnt}[v]+=\text{cnt}[u]$ over incoming edges in topo order. To count shortest paths in a weighted graph that may have cycles (Number of Ways to Arrive at Destination), process vertices in non-decreasing distance order (the order Dijkstra finalizes them, which is a topological order of the shortest-path DAG) and carry a parallel count:

The distance DP finds the best value; the count DP, evaluated in the same order, tallies how many ways achieve it.

Warshall's transitive closure: the boolean analog

Replace shortest distance with is there any path, and $\min /+$ with $\vee /\wedge$, and Floyd–Warshall becomes Warshall's transitive-closure algorithm. Let $r_k[i][j]$ be true iff $j$ is reachable from $i$ using intermediate vertices in $\{1,\dots ,k\}$:

Same triple loop, same $O(V^3)$, same in-place collapse of the $k$ index; only the semiring changed (booleans under or/and instead of reals under min/plus). Course Schedule IV is this exactly: prerequisites form a DAG, and each query is course $a$ a prerequisite of course $b$? is a lookup in the reachability matrix $r_V$.

Held–Karp: a subset as the resource

The resource need not be a single number. In Held–Karp bitmask TSP (the Bitmask DP lesson), the subproblem is $D[S][v]$ = the cheapest path starting at the origin, visiting exactly the vertex set $S$, and ending at $v$; the transition relaxes over the last hop $D[S][v]={\min }_{u\in S\setminus \{v\}}D[S\setminus \{v\}][u]+w(u,v)$. The rationed resource is the subset of visited vertices, grown one vertex per layer, the same skeleton as Floyd–Warshall, with $2^V$ subsets in place of $V$ intermediate-vertex levels. Shortest Path Visiting All Nodes is the unweighted cousin: a BFS over $(\text{mask},v)$ states, where the mask is again the resource. The DP-on-graphs lens scales from one scalar of slack all the way up to an exponential subset.

Choosing the framing

All four are DP, but the right resource depends on the graph:

• Floyd–Warshall: dense, all-pairs, negative edges allowed; $O(V^3)$ time, $O(V^2)$ space. The default when you need every pair.
• $V\times$ Dijkstra: sparse graphs with non-negative weights; $O(V(E+V\log V))$, which beats $V^3$ when $E\ll V^2$.
• Bellman–Ford: single-source with negative edges, negative-cycle detection, or an edge-count cap ($K$-stops); $O(VE)$.
• DAG-DP: acyclic graphs; $O(V+E)$, handles negative weights and even longest paths, because topological order removes the need to iterate to convergence.

Takeaways

• Many graph algorithms are dynamic programs. The subproblem is the best value under a restricted resource (intermediate vertices, edges, a topological prefix, or a visited subset), and edge relaxation is the DP transition.
• Floyd–Warshall is the archetype: $d_k[i][j]=\min (d_{k-1}[i][j],d_{k-1}[i][k]+d_{k-1}[k][j])$, route through $k$ or don't, collapsing in place to $O(V^3)$ time, $O(V^2)$ space; negative edges OK, and $d[i][i]<0$ flags a negative cycle.
• Bellman–Ford is a DP over path length, $D_t[v]$ for at-most-$t$ edges; $V-1$ rounds converge, an extra relaxation detects a negative cycle, and capping $t$ at $K+1$ solves Cheapest Flights Within K Stops ($O(VE)$).
• DAG-DP processes vertices in topological order for an $O(V+E)$ single pass, shortest or longest path, and counting (shortest) paths by carrying a count alongside the distance.
• Warshall's transitive closure is the boolean Floyd–Warshall ($\vee /\wedge$), giving reachability, exactly Course Schedule IV.
• The resource can be a subset (Held–Karp / bitmask TSP), unifying scalar shortest paths with exponential-state DP under one frame.