Dynamic Programming

Dynamic approach for all-pair shortest path

We can also solve the all-pairs shortest path problem directly using dynamic programming instead of invoking a single-source algorithm. For dense graphs, where $E = Ω(V2)$, the dynamic programming approach eventually yields an algorithm that is both simpler and (slightly) faster than Johnson’s algorithm. For the rest of this course, we will assume that the input graph contains no negative cycles.

As usual, for dynamic programming algorithms, we first need a recurrence. Just as in the single-source setting, the obvious recursive definition,

$$dist(u,v) = \begin{cases} & 0 \hspace{4.39cm}\text{ if }u = v \\ & \underset{x\rightarrow v}{min} (dist(u,x) + w(x\rightarrow v)) \hspace{0.4cm} otherwise \end{cases}$$

only works when the input graph is a dag; any directed cycles drive the recurrence into an infinite loop.

We can break this infinite loop by introducing an additional parameter, exactly as we did for Bellman-Ford; let $dist(u, v, l)$ denote the length of the shortest path from $u$ to $v$ that uses at most $l$ edges. The shortest path between any two vertices traverses at most $V −1$ edges, so the true shortest path distance is $dist(u, v, V − 1)$. Bellman’s single-source recurrence adapts to this setting immediately:

$$dist(u,v,l) = \begin{cases} & 0 \hspace{6.5cm}\text{ if } l\text{ = 0 and } u=v\\ & \infty \hspace{6.34cm}\text{ if } l\text{ = 0 and } u\neq v \\ & min\begin{Bmatrix} dist(u,v,l-1) \\ \underset{x\rightarrow v}{min} (dist(u,x,l-1) + w(x\rightarrow v)) \\ \end{Bmatrix} \hspace{0.4cm} otherwise \end{cases}$$

Recurrence into dynamic programming

Turning this recurrence into a dynamic programming algorithm is straightforward; the resulting algorithm runs in $O(V^2E) = O(V^4)$ time.