---
title: Dynamic Programming on Graphs
module: Dynamic Programming
moduleNumber: 8
lessonNumber: 10
order: 810
summary: |
  Many graph algorithms are dynamic programs: the subproblem is the
  _best value reachable under a restricted resource_ — intermediate vertices
  allowed, edges allowed, or a topological prefix — and edge _relaxation_ is the
  DP transition. We frame Floyd–Warshall as the archetype ($O(V^3)$ all-pairs
  shortest paths), Bellman–Ford as a DP over path length (the at-most-$K$-stops
  variant), DAG-DP in topological order ($O(V+E)$), and Warshall's transitive
  closure as the boolean analog.
topics: [Dynamic Programming]
sources:
  - book: CLRS
    ref: "Ch. 23 — All-Pairs Shortest Paths (§23.2 Floyd–Warshall)"
  - book: Skiena
    ref: "§ — Shortest Paths / DP"
  - book: Erickson
    ref: "Ch. — Dynamic Programming"
practice:
  - title: 'Find the City With the Smallest Number of Neighbors at a Threshold Distance'
    slug: find-the-city-with-the-smallest-number-of-neighbors-at-a-threshold-distance
    difficulty: Medium
  - title: 'Course Schedule IV'
    slug: course-schedule-iv
    difficulty: Medium
  - title: 'Number of Ways to Arrive at Destination'
    slug: number-of-ways-to-arrive-at-destination
    difficulty: Medium
  - title: 'Cheapest Flights Within K Stops'
    slug: cheapest-flights-within-k-stops
    difficulty: Medium
  - title: 'Shortest Path Visiting All Nodes'
    slug: shortest-path-visiting-all-nodes
    difficulty: Hard
---

The Graphs module's [Shortest Paths](/algorithms/graphs/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](/algorithms/dynamic-programming/principles)
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](/algorithms/dynamic-programming/bitmask-dp) lesson).

Relaxing an edge $(u,v)$, testing whether routing through $u$ improves the
current estimate for $v$, is the $\min$ over choices in a DP recurrence.
Under this framing, "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.[^erickson-dp]

## 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.

> **Definition.** Let $d_k[i][j]$ be the weight of a shortest path from $i$ to
> $j$ all of whose **intermediate** vertices lie in $\{1,\dots,k\}$ (the
> endpoints $i,j$ are unrestricted). Then $d_V[i][j]$ is the true all-pairs
> shortest distance, and $d_0$ is just the weight matrix.

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.

> **Lemma (optimal substructure).** A shortest $i\rightsquigarrow j$ path with
> intermediate vertices drawn from $\{1,\dots,k\}$ either **does not use** $k$,
> in which case it is a shortest path through $\{1,\dots,k-1\}$, or it **uses
> $k$ exactly once**, splitting into a shortest $i\rightsquigarrow k$ path and a
> shortest $k\rightsquigarrow j$ path, each through $\{1,\dots,k-1\}$.

> **Proof.** Consider a shortest such path $p$. If $k$ is not an intermediate
> vertex of $p$, all its intermediate vertices already lie in $\{1,\dots,k-1\}$.
> Otherwise decompose $p$ at $k$ into $p_1 : i\rightsquigarrow k$ and
> $p_2 : k\rightsquigarrow j$. Since the graph has no negative cycle, no
> shortest path repeats a vertex, so $k$ appears only at the split and the
> intermediate vertices of $p_1$ and $p_2$ lie in $\{1,\dots,k-1\}$. Each leg
> must itself be shortest (a cheaper leg would cheapen $p$), giving the
> two-term option. $\qed$

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

$$
d_k[i][j] = \min\parens{\,\underbrace{d_{k-1}[i][j]}_{\text{avoid }k},\ \underbrace{d_{k-1}[i][k] + d_{k-1}[k][j]}_{\text{through }k}\,}.
$$

$$
% caption: route through $k$, or don't — the Floyd–Warshall $\min$
\begin{tikzpicture}[
  every node/.style={circle, draw, minimum size=8mm, inner sep=0},
  >=stealth]
  \definecolor{acc}{HTML}{2348F2}
  \node (i) at (0,0) {$i$};
  \node (j) at (5,0) {$j$};
  \node (k) at (2.5,1.8) {$k$};
  % direct option (curved below, plain)
  \draw[->, bend right=22] (i) to node[draw=none, below=0.5mm, font=\footnotesize, pos=0.5] {\texttt{d[k-1][i][j]}} (j);
  % through-k option, highlighted
  \draw[->, thick, acc] (i) -- node[draw=none, above left=-1mm, font=\footnotesize] {\texttt{d[k-1][i][k]}} (k);
  \draw[->, thick, acc] (k) -- node[draw=none, above right=-1mm, font=\footnotesize] {\texttt{d[k-1][k][j]}} (j);
  \node[draw=none, font=\footnotesize] at (2.5,-2.2) {\texttt{d[k][i][j] = min(direct, through k)}};
\end{tikzpicture}
$$

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:

```algorithm
caption: $\textsc{Floyd-Warshall}(W)$ — all-pairs shortest paths in $O(V^3)$
$d \gets W$ // $w(i,j)$; $0$ on diagonal, else $\infty$
for $k \gets 1$ to $V$ do
  for $i \gets 1$ to $V$ do
    for $j \gets 1$ to $V$ do
      if $d[i][k] + d[k][j] < d[i][j]$ then
        $d[i][j] \gets d[i][k] + d[k][j]$
        $\text{next}[i][j] \gets \text{next}[i][k]$ // for reconstruction
return $d$
```

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.[^clrs-fw]

> **Remark (negative edges).** The derivation never assumed non-negative weights,
> only the _absence of negative cycles_ (used to argue shortest paths are
> simple). So Floyd–Warshall handles negative edges directly, unlike Dijkstra.
> And it **detects** a negative cycle for free: after the algorithm, a negative
> cycle exists iff $d[i][i] < 0$ for some $i$, meaning some vertex can reach
> itself at negative cost.

For a worked example, take four vertices with the weight matrix (rows are
sources, $\infty$ where no direct edge exists):

$$
d_0 =
\begin{pmatrix}
0 & 3 & \infty & 7\\
8 & 0 & 2 & \infty\\
5 & \infty & 0 & 1\\
2 & \infty & \infty & 0
\end{pmatrix}
\qquad\longrightarrow\qquad
d_4 =
\begin{pmatrix}
0 & 3 & 5 & 6\\
5 & 0 & 2 & 3\\
3 & 6 & 0 & 1\\
2 & 5 & 7 & 0
\end{pmatrix}
$$

Each level admits one more intermediate vertex. Allowing vertex $1$ ($k=1$) fixes
$d[2][4]$: the direct entry was $\infty$, but $2 \to 1 \to 4$ is not yet
improved — rather $d[4][2]$ becomes $2 + 3 = 5$ through vertex $1$, and
$d[3][2] = 5 + 3 = 8$. Allowing vertex $2$ ($k=2$) sets $d[1][3] = d[1][2] +
d[2][3] = 3 + 2 = 5$ and $d[4][3] = d[4][2] + d[2][3] = 5 + 2 = 7$. Allowing
vertex $3$ ($k=3$) improves $d[1][4]$ to $d[1][3] + d[3][4] = 5 + 1 = 6$ and
$d[2][1]$ to $d[2][3] + d[3][1] = 2 + 5 = 7$. The last level ($k=4$) routes
through vertex $4$ to drop $d[2][1]$ further to $3 + 2 = 5$ and $d[3][1]$ to
$2 + 1 = 3$. Reading $d_4$ off gives every pairwise shortest distance at once.

$$
% caption: Floyd-Warshall on four vertices: the base matrix $d_0$ (direct edges only)
%          relaxes level by level; the $k=1$ pass fills $d[4][2]=5$ via vertex 1,
%          shaded, illustrating the route-through-k update.
\begin{tikzpicture}[
  cell/.style={draw, minimum size=8mm, inner sep=1pt, font=\footnotesize},
  >=stealth]
  \definecolor{acc}{HTML}{2348F2}
  % base matrix d0
  \node[font=\footnotesize] at (1.8,2.2) {base \texttt{d0}};
  % render base rows explicitly ("." marks no direct edge / infinity)
  \foreach \i/\a/\b/\c/\dd in {0/0/3/./7, 1/8/0/2/., 2/5/./0/1, 3/2/./././0} {
    \node[cell] at (0.5,1.5-\i*0.8) {\texttt{\a}};
    \node[cell] at (1.3,1.5-\i*0.8) {\texttt{\b}};
    \node[cell] at (2.1,1.5-\i*0.8) {\texttt{\c}};
    \node[cell] at (2.9,1.5-\i*0.8) {\texttt{\dd}};
  }
  % arrow between the two matrices
  \draw[->, thick] (3.5,0.3) -- (4.7,0.3);
  % final matrix d4
  \node[font=\footnotesize] at (6.6,2.2) {f\/inal \texttt{d4}};
  \foreach \i/\a/\b/\c/\dd in {0/0/3/5/6, 1/5/0/2/3, 2/3/6/0/1, 3/2/5/7/0} {
    \node[cell] at (5.3,1.5-\i*0.8) {\texttt{\a}};
    \node[cell] at (6.1,1.5-\i*0.8) {\texttt{\b}};
    \node[cell] at (6.9,1.5-\i*0.8) {\texttt{\c}};
    \node[cell] at (7.7,1.5-\i*0.8) {\texttt{\dd}};
  }
  \node[font=\footnotesize] at (1.7,-1.9) {\texttt{.} marks no direct edge};
\end{tikzpicture}
$$

**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.

::impl{algo="transitive_closure"}

## 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.

> **Definition.** Let $D_t[v]$ be the shortest distance from the source $s$ to
> $v$ using a path of **at most $t$ edges**. Then $D_0[s]=0$, $D_0[v]=\infty$
> otherwise.

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)$:

$$
D_t[v] = \min\parens{D_{t-1}[v],\ \min_{(u,v)\in E} D_{t-1}[u] + w(u,v)}.
$$

Each round is one full sweep of edge relaxations, the same 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.[^clrs-bf] 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 just $D_{K+1}[t]$:
run exactly $K+1$ Bellman–Ford rounds, no more.

$$
% caption: Bellman–Ford as a DP over path length: $D_t[v]$ = cheapest $s\to v$ using
%          $\le t$ edges; each round relaxes against the previous layer, so capping $t$
%          solves the $K$-stops variant
\begin{tikzpicture}[
  cell/.style={draw, minimum width=9mm, minimum height=7mm, inner sep=1pt, font=\footnotesize},
  >=stealth]
  \definecolor{acc}{HTML}{2348F2}
  \foreach \c/\lab in {1/s,2/a,3/b,4/t} {
    \node[font=\footnotesize] at (\c*1.0+0.4,0.7) {$\lab$};
  }
  \foreach \r/\lab in {0/{t{=}0},1/{t{=}1},2/{t{=}2},3/{t{=}3}} {
    \node[font=\footnotesize] at (0.4,-\r*0.75) {$\lab$};
  }
  \foreach \c/\v in {1/$0$,2/$\infty$,3/$\infty$,4/$\infty$} \node[cell] at (\c*1.0+0.4,0) {\v};
  \foreach \c/\v in {1/$0$,2/$4$,3/$5$,4/$\infty$} \node[cell] at (\c*1.0+0.4,-0.75) {\v};
  \node[cell] at (1.4,-1.5) {$0$};
  \node[cell] at (2.4,-1.5) {$4$};
  \node[cell, fill=acc!15] at (3.4,-1.5) {$2$};
  \node[cell] at (4.4,-1.5) {$8$};
  \node[cell] at (1.4,-2.25) {$0$};
  \node[cell] at (2.4,-2.25) {$4$};
  \node[cell] at (3.4,-2.25) {$2$};
  \node[cell, fill=acc!15] at (4.4,-2.25) {$5$};
  \node[font=\footnotesize, acc] at (7.0,-1.5) {\texttt{b: 4 - 2 = 2}};
  \node[font=\footnotesize, acc] at (7.0,-2.25) {\texttt{t: 2 + 3 = 5}};
\end{tikzpicture}
$$

> **Remark (snapshot the layer).** With the $K$-stops cap you must relax against
> the _previous_ layer $D_{t-1}$, not the layer being filled, since otherwise a path
> updated earlier in the same sweep could be reused, adding an extra edge.
> Copy $D_{t-1}$ before each round (or relax the original edge list into a fresh
> array). The unbounded version may safely update in place, since extra
> relaxations only help once the edge budget is irrelevant.

A concrete _Cheapest Flights Within K Stops_ instance shows why the cap matters.
Take cities $s, a, b, t$ with directed flights $s \to a$ (cost $100$),
$a \to t$ (cost $100$), $s \to b$ (cost $500$), $b \to t$ (cost $50$), and the
much cheaper two-leg detour $s \to a \to t$ competing against the direct-ish
$s \to b \to t$. Ask for the cheapest $s \to t$ route with at most $K = 1$ stop,
that is at most $2$ edges, so we run exactly $K + 1 = 2$ rounds, each relaxing
against the frozen previous layer:

| layer | $s$ | $a$ | $b$ | $t$ |
|:--|:--:|:--:|:--:|:--:|
| $D_0$ | $0$ | $\infty$ | $\infty$ | $\infty$ |
| $D_1$ | $0$ | $100$ | $500$ | $\infty$ |
| $D_2$ | $0$ | $100$ | $500$ | $\min(100{+}100,\ 500{+}50) = 200$ |

Round $1$ reaches the one-edge neighbors $a$ and $b$. Round $2$ reaches $t$ two
ways — $s\to a\to t = 200$ and $s\to b\to t = 550$ — and keeps $200$. The
answer is $200$, using exactly $2$ edges (one stop). A cheaper $3$-edge route, had
one existed, would be invisible here precisely because we stopped after $2$ rounds:
the cap is enforced by the round count, and freezing $D_1$ before round $2$ is what
prevents $t$ from being reached in a single sweep through both edges.

::impl{algo="bounded_bellman_ford"}

## DAG-DP: a topological prefix as the resource

When the graph is **acyclic**, the resource becomes trivial to ration: process
vertices in
[topological order](/algorithms/graphs/topological-sort-and-scc). 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.

```algorithm
caption: $\textsc{DAG-Relax}(G, s)$ — shortest/longest paths on a DAG in $O(V+E)$
$\text{topologically sort } G$
$D[v] \gets \infty$ for all $v$;  $D[s] \gets 0$
for each $u$ in topological order do
  for each edge $(u,v)$ do
    if $D[u] + w(u,v) < D[v]$ then  // use $\max$ for longest path
      $D[v] \gets D[u] + w(u,v)$
return $D$
```

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.[^skiena-dag]

$$
% caption: one pass in topo order — longest-path values, chosen edge in $acc$
\begin{tikzpicture}[
  every node/.style={circle, draw, minimum size=9mm, inner sep=0, font=\small},
  >=stealth, node distance=14mm]
  \definecolor{acc}{HTML}{2348F2}
  \node (a) at (0,0) {$a$};
  \node (b) at (2.4,0.9) {$b$};
  \node (c) at (2.4,-0.9) {$c$};
  \node (d) at (4.8,0) {$d$};
  % values above each node
  \node[draw=none, font=\footnotesize] at (0,1.0) {$0$};
  \node[draw=none, font=\footnotesize] at (2.4,1.9) {$3$};
  \node[draw=none, font=\footnotesize] at (2.4,-1.9) {$2$};
  \node[draw=none, font=\footnotesize] at (4.8,1.0) {$7$};
  \draw[->] (a) -- node[draw=none, above left=-1.5mm, font=\footnotesize] {$3$} (b);
  \draw[->] (a) -- node[draw=none, below left=-1.5mm, font=\footnotesize] {$2$} (c);
  \draw[->, thick, acc] (b) -- node[draw=none, above right=-1.5mm, font=\footnotesize] {$4$} (d);
  \draw[->] (c) -- node[draw=none, below right=-1.5mm, font=\footnotesize] {$1$} (d);
\end{tikzpicture}
$$

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** uses the same order. To count _all_ paths $s\to t$ in a
DAG, set $\text{cnt}[s]=1$ and accumulate
$\text{cnt}[v] \mathrel{+}= \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:

$$
\text{when } D[u] + w(u,v) = D[v]:\ \ \text{cnt}[v] \mathrel{+}= \text{cnt}[u]
\quad(\text{a strict improvement instead } \textit{resets } \text{cnt}[v]).
$$

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

::impl{algo="dag_longest_path,dag_path_count,shortest_path_count"}

$$
% caption: Counting $s\to t$ paths in topo order: $\text{cnt}[s]=1$, then
%          $\text{cnt}[v]\mathrel{+}=\text{cnt}[u]$ over incoming edges — here
%          $\text{cnt}[t]=1+2=3$
\begin{tikzpicture}[
  every node/.style={circle, draw, minimum size=9mm, inner sep=0, font=\small},
  >=stealth]
  \definecolor{acc}{HTML}{2348F2}
  \node (s) at (0,0) {$s$};
  \node (a) at (2.2,1.1) {$a$};
  \node (b) at (2.2,-1.1) {$b$};
  \node[draw=acc, very thick, text=acc] (t) at (4.4,0) {$t$};
  \draw[->] (s) -- (a);
  \draw[->] (s) -- (b);
  \draw[->] (a) -- (b);
  \draw[->] (a) -- (t);
  \draw[->] (b) -- (t);
  \node[draw=none, font=\footnotesize] at (0,0.85) {$\text{cnt}{=}1$};
  \node[draw=none, font=\footnotesize] at (2.2,1.95) {$\text{cnt}{=}1$};
  \node[draw=none, font=\footnotesize] at (2.2,-1.95) {$\text{cnt}{=}2$};
  \node[draw=none, font=\footnotesize, acc] at (4.4,0.95) {$\text{cnt}{=}3$};
\end{tikzpicture}
$$

## Warshall's transitive closure: the boolean analog

Replace "shortest distance" with "is there _any_ path", and $\min/+$ with
$\lor/\land$, 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\}$:

$$
r_k[i][j] = r_{k-1}[i][j]\ \lor\ \parens{r_{k-1}[i][k]\ \land\ r_{k-1}[k][j]}.
$$

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 very problem: 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](/algorithms/dynamic-programming/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 same framing scales from a single scalar resource 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.

## The algebraic view and its descendants

The unification in this lesson is an
instance of an algebraic fact. Floyd–Warshall, Warshall's closure, and even the
path-counting variant are all the **same algorithm over different semirings**. A
semiring supplies a "$+$" that combines alternatives and a "$\times$" that
concatenates a path in sequence: for shortest paths $(\min, +)$, for reachability
$(\lor, \land)$, for path counting $(+, \times)$, for widest-path / bottleneck
routing $(\max, \min)$. Replace the operators and the triple loop computes the
corresponding closure without any other change. This is the **algebraic path
problem**, developed by Backhouse and Carré (1975) and by Lehmann (1977), and it
explains why "cheapest", "is there any", and "how many" are the same
exercise: one program parameterized by a semiring.[^semiring]

The same all-pairs closure connects to linear algebra through **matrix
multiplication over the $(\min, +)$ semiring** (the "min-plus" or _tropical_
product). All-pairs shortest paths equals the $(V{-}1)$-th tropical power of the
weight matrix, computable by repeated squaring in $O(V^3 \log V)$ — slower than
Floyd–Warshall's $O(V^3)$, but the connection underlies the theory of
**subcubic** all-pairs shortest paths. Williams (2014) gave the first truly
subcubic APSP, running in $O(V^3 / 2^{\Theta(\sqrt{\log V})})$; whether a genuinely
polynomially-faster ($O(V^{3-\varepsilon})$) algorithm exists is a central open
question, tied by fine-grained complexity to the (min,+)-matrix-multiplication and
Boolean-matrix-multiplication conjectures.

Held and Karp's subset DP for TSP (Held and Karp, 1962, _J. SIAM_) remains, sixty
years on, the fastest known _exact_ TSP algorithm in the worst case at
$O(2^n n^2)$ time — no algorithm with a better exponential base is known, which
indicates how hard exact TSP is. On the practical side, the DAG shortest
path with a topological order underlies **critical-path scheduling**
(PERT/CPM): the longest path through a task-dependency DAG is the minimum project
completion time, and it is computed by exactly the $\max$ variant of `DAG-Relax`
above. And the layered Bellman–Ford view — relax against the previous layer,
snapshotting each round — is the shape of the **Viterbi algorithm** for hidden
Markov models, where each "layer" is a time step and the DP finds the most likely
state sequence.

## 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
  ($\lor/\land$), 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.

[^erickson-dp]: **Erickson**, Ch. — Dynamic Programming: the DP recipe is to define the subproblem, write the recurrence, and evaluate in an order respecting the dependency DAG.
[^clrs-fw]: **CLRS**, Ch. 23 — All-Pairs Shortest Paths (§23.2): Floyd–Warshall's intermediate-vertex recurrence, $\Theta(V^3)$ in-place evaluation, and negative-cycle detection via $d[i][i]<0$.
[^clrs-bf]: **CLRS**, Ch. 22 — Single-Source Shortest Paths: Bellman–Ford relaxes all edges $V-1$ times; a further relaxation reveals a negative cycle.
[^skiena-dag]: **Skiena**, § — Shortest Paths / DP: shortest and longest paths on a DAG in $O(V+E)$ by relaxing edges in topological order; longest path is NP-hard only in general graphs.
[^semiring]: **Backhouse & Carré** (1975) and **Lehmann** (1977) on the algebraic path problem: Floyd–Warshall, transitive closure, and path counting are one closure algorithm over different semirings ($(\min,+)$, $(\lor,\land)$, $(+,\times)$). See **Williams** (2014, STOC) for subcubic APSP via min-plus matrix products, and **Held & Karp** (1962, _J. SIAM_ 10) for the $O(2^n n^2)$ exact-TSP subset DP.