Dynamic Programming

Explore how dynamic programming can be used to optimize the all-pairs shortest paths algorithms.

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)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)={0 if u=vminxv(dist(u,x)+w(xv))otherwisedist(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)dist(u, v, l) denote the length of the shortest path from uu to vv that uses at most ll edges. The shortest path between any two vertices traverses at most V1V −1 edges, so the true shortest path distance is dist(u,v,V1)dist(u, v, V − 1). Bellman’s single-source recurrence adapts to this setting immediately:

dist(u,v,l)={0 if l = 0 and u=v if l = 0 and uvmin{dist(u,v,l1)minxv(dist(u,x,l1)+w(xv))}otherwisedist(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(V2E)=O(V4)O(V^2E) = O(V^4) time.

Create a free account to access the full course.

By signing up, you agree to Educative's Terms of Service and Privacy Policy