Dynamic Programming Shortest Path Problem
Example : Shortest Path Problem in Dynamic Programming
The MD of Universal Teacher Publications wants to visit the Bell Well temple. Consider the following diagram where circles denote states, and lines between two such circles represent highways connecting the states. The numbers inside the circles represent state numbers, and those given beside the lines denote the distances between the states connected by the lines. The problem is to find the shortest route from state 1 to state 10 where the Bell Well temple is situated.
Solution.
For a systematic approach to dynamic programming problem, consider the following notations.
n = number of stages.
s = state variable.
dsj = immediate distance from entering state s to existing
state j.
fn(s) = the overall optimal objective function with n more
stages to go when he is in state s.
jn(s) = a decision yielding fn(s).
Notice that the entire trip from state 1 to state 10 requires four stages (highways), regardless of the particular routing. Now, the problem is to select these four highways so that the total distance covered is least. The first highway has to be chosen from 1-2, 1-3, or 1-4, as 1 is the starting state. Likewise, the second highway has to be chosen from 2, 3, or 4, the third from 5, 6, or 7 and the fourth from 8 or 9.
There is one table for each possible stage n, namely, n = 1, 2, 3, and 4. We start calculating distances between pair of states from stage 4 backwards. At the beginning of stage 4, we can be in either 8 or 9 (states). We note that state 10 is the only destination from both states 8 & 9. We summarize this information in the format below.
Stage 4 (n = 1)
| State | Decision (j) |
Best decision | Best distance |
|---|---|---|---|
| (s) | 10 | j1(s) | f1(s) |
| 8 | 9 + 0 | 10 | 9 |
| 9 | 6 + 0 | 10 | 6 |
Stage 3 (n = 2)
| State | Decision (j) | Best Decision | Best Distance | |
|---|---|---|---|---|
| (s) | 8 | 9 | j2(s) | f2(s) |
| 5 | 6 + 9 = 15 | 8 + 6 = 14 | 9 | 14 |
| 6 | 4 + 9 = 13 | 9 + 6 = 15 | 8 | 13 |
| 7 | 3 + 9 = 12 | 7 + 6 = 13 | 8 | 12 |
The entries in second & third column are the sum of the immediate distance dsj to go from state s to state j. In each row, we examine the sums to find the smallest. Observe that f1(8) = 9 is added to each ds8 in the j = 8 column and f1(9) = 6 is added to each ds9 in the j = 9 column. The above table shows that with two stages left it is optimal to go to state 9 from state 5, and state 8 from states 6 & 7.
The analysis for n = 3 appears in the following table.
Stage 2 (n = 3)
| State | Decision (j) | Best Decision | Best Distance | ||
|---|---|---|---|---|---|
| (s) | 5 | 6 | 7 | j3(s) | f3(s) |
| 2 | 6 + 14 = 20 | 8 + 13 = 21 | 9 + 12 = 21 | 5 | 20 |
| 3 | 5 + 14 = 19 | 4 + 13 = 17 | 6 + 12 = 18 | 6 | 17 |
| 4 | 5 + 14 = 19 | 5 + 13 = 18 | 7 + 12 = 19 | 6 | 18 |
Stage 1 (n = 4)
| State | Decision (j) | Best Decision | Best Distance | ||
|---|---|---|---|---|---|
| (s) | 2 | 3 | 4 | j4(s) | f4(s) |
| 1 | 4 + 20= 24 | 6 + 17 = 23 | 6 + 18 = 24 | 3 | 23 |
The computations terminate in the above table with n = 4. The shortest route from state 1 to state 10 is given by 1-3-6-8-10, and the distance to be covered is 23.
