7.2.2 Dynamic Programming Algorithm

REF.

Richard Bellman. Dynamic Programming. Princeton University Press, 1957.

REF.

Richard Bellman. On a routing problem. Quarterly of Applied Mathematics, Volume 16, Number 1, pp. 87-90, 1958.

Consider a directed acyclic graph (digraph without cycles) with nonnegative weights on the directed arcs.

Given a destination vertex z, the problem is to find a shortest cost path from each vertex of the digraph. See Figure 7.6.

Let

$$\mbox{Cost of the directed arcfrom vertex $i$\space to }$$ C(i, j) =

$$\mbox{vertex $j$\space ($ \infty$\space in case there is no link)}$$ (7.8)

$$\mbox{Optimal cost of a path from vertex $i$ , to the }$$ J(i) = (7.9)

$$\mbox{destination vertex $z$ }$$

J(i) Satisfies :

J(z) = 0 and if the optimal path from i to z traverses the link (i, j) then J(i) = C(i, j) + J(j)

Figure 7.6: Principle of dynamic programming

Suppose that for each vertex j such that the link (i, j) exists, the optimal cost J(j) is known. Then, the principle of DP immediately implies:

J(i) = $$\min_{j}^{}$$ [C(i, j) + J(j)] A DP algorithm based on the above observations:

1.

Set J(z) = 0. At this point, this is the only node whose cost has been computed.

2.

Consider vertices i $\in$V such that

• J(i) has not yet been found
• for each vertex j such that a link (i, j) exists, J(j) is already computed

Assign J(i) according to 

            J(i) = $$\min_{j}^{}$$[C(i, j) + J(j)]

3.

Repeat Step 2 until all vertices have their optimal costs computed.

Example: Consider the digraph in Figure 7.7
 
 

Figure 7.7: An example digraph to illustrate dynamic programming

Step 1.

J(Z) = 0

Step 2.

E is the only vertex such that J(j) is known $\forall$I>j such that C(E, j) $\neq$ 0

J(E) = C(E, Z) + J(Z) = 1

Step 3.

Select F.

$$\left\{\vphantom{\begin{array}{c}C(F,Z) + J(Z) = 5 \\ C(F,E) + J(E) = 3 \end{array} }\right. \begin{array}{c}C(F,Z) + J(Z) = 5 \\ C(F,E) + J(E) = 3 \end{array} \left.\vphantom{\begin{array}{c}C(F,Z) + J(Z) = 5 \\ C(F,E) + J(E) = 3 \end{array} }\right.$$ J(F) = (7.10)

= min(5, 3) = 3

This yields the optimal path F$\rightarrow$E$\rightarrow$Z.

Step 4.

Select C.

$$\left\{\vphantom{\begin{array}{c}C(C,E) + J(E) = 8 \\ C(C,F) + J(F) = 6 \end{array} }\right. \begin{array}{c}C(C,E) + J(E) = 8 \\ C(C,F) + J(F) = 6 \end{array} \left.\vphantom{\begin{array}{c}C(C,E) + J(E) = 8 \\ C(C,F) + J(F) = 6 \end{array} }\right.$$ J(C) = (7.11)

= min(8, 6) = 6

This yields the optimal path C$\rightarrow$F$\rightarrow$E$\rightarrow$Z.

Step 5.

Select D

J(D) = min$$\left\{\vphantom{\begin{array}{l} C(D,C) + J(C) = 7 \\ C(D,E) + J(E) = 3 \\space \ \space = 3 \\ C(D,F) + J(F) = 4 \end{array} }\right.$$$$\begin{array}{l} C(D,C) + J(C) = 7 \\ C(D,E) + J(E) = 3 \\space \ \space = 3 \\ C(D,F) + J(F) = 4 \end{array}$$$$\left.\vphantom{\begin{array}{l} C(D,C) + J(C) = 7 \\ C(D,E) + J(E) = 3 \\space \ \space = 3 \\ C(D,F) + J(F) = 4 \end{array} }\right.$$ This yields the optimal path D$\rightarrow$E$\rightarrow$Z.

$\vdots$

Eventually, we get all the optimal paths and all the optimal costs.

Complexity of the Algorithm

• It is easy to see that the algorithm has a worst case complexity of O(n²), where n is the number of vertices.
• Limitation of the algorithm
• doesn't work if there are cycles in the digraph.