The Shortest Route Problem
 Example
The MD of  www.universalteacher.com
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.
|
