![next](http://lcm.csa.iisc.ernet.in/dsa/next_motif.gif)
![up](http://lcm.csa.iisc.ernet.in/dsa/up_motif.gif)
Next:7.2.3
All Pairs Shortest Paths Problem: Floyd's AlgorithmUp:7.2
Shortest Paths ProblemPrevious:7.2.1
Single Source Shortest Paths Problem: Dijkstra's Algorithm
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
C(i, j) |
= |
![$\displaystyle \mbox{Cost of the directed arcfrom vertex $i$\space to }$](img326.gif) |
|
|
|
![$\displaystyle \mbox{vertex $j$\space ($ \infty$\space in case there is no link)}$](img327.gif) |
(7.8) |
J(i) |
= |
![$\displaystyle \mbox{Optimal cost of a path from vertex $i$ , to the }$](img328.gif) |
(7.9) |
|
|
![$\displaystyle \mbox{destination vertex $z$ }$](img329.gif) |
|
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
![\begin{figure}\centerline{\psfig{figure=figures/Fdp1.ps}}\end{figure}](img330.gif) |
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) =
[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
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) =
[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
![\begin{figure}\centerline{\psfig{figure=figures/Fdp2.ps}}\end{figure}](img332.gif) |
-
Step 1.
-
J(Z) = 0
-
Step 2.
-
E is the only vertex such that J(j) is known
I>j
such that C(E, j)
0
J(E) = C(E, Z) + J(Z)
= 1
-
Step 3.
-
Select F.
J(F) |
= |
min![$\displaystyle \left\{\vphantom{\begin{array}{c}C(F,Z) + J(Z) = 5 \\ C(F,E) + J(E) = 3 \end{array} }\right.$](img333.gif) ![$\displaystyle \begin{array}{c}C(F,Z) + J(Z) = 5 \\ C(F,E) + J(E) = 3 \end{array}$](img334.gif) ![$\displaystyle \left.\vphantom{\begin{array}{c}C(F,Z) + J(Z) = 5 \\ C(F,E) + J(E) = 3 \end{array} }\right.$](img335.gif) |
(7.10) |
|
= |
min(5, 3) = 3 |
|
This yields the optimal path F
E
Z.
-
Step 4.
-
Select C.
J(C) |
= |
min![$\displaystyle \left\{\vphantom{\begin{array}{c}C(C,E) + J(E) = 8 \\ C(C,F) + J(F) = 6 \end{array} }\right.$](img336.gif) ![$\displaystyle \begin{array}{c}C(C,E) + J(E) = 8 \\ C(C,F) + J(F) = 6 \end{array}$](img337.gif) ![$\displaystyle \left.\vphantom{\begin{array}{c}C(C,E) + J(E) = 8 \\ C(C,F) + J(F) = 6 \end{array} }\right.$](img338.gif) |
(7.11) |
|
= |
min(8, 6) = 6 |
|
This yields the optimal path C
F
E
Z.
-
Step 5.
-
Select D
J(D) = min![$\displaystyle \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.$](img339.gif)
![$\displaystyle \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}$](img340.gif)
This yields the optimal path D
E
Z.
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(n2),
where n is the number of vertices.
-
Limitation of the algorithm
-
doesn't work if there are cycles in the digraph.
![next](http://lcm.csa.iisc.ernet.in/dsa/next_motif.gif)
![up](http://lcm.csa.iisc.ernet.in/dsa/up_motif.gif)
Next:7.2.3
All Pairs Shortest Paths Problem: Floyd's AlgorithmUp:7.2
Shortest Paths ProblemPrevious:7.2.1
Single Source Shortest Paths Problem: Dijkstra's Algorithm
eEL,CSA_Dept,IISc,Bangalore