Example 1: Shortest Path
Example: How to Solve
In order to solve this problem we must look at it in terms of nodes and stages. The stages (levels) and nodes(points) we must consider are as follows:
- Stage 1: Node A (Origin point)
- Stage 2: Node B, C, D
- Stage 3: Node E, F, G
- Stage 4: Node H, I
- Stage 5: Node J (Termination point)
If S is allowed to denote a node in stage j and we let f_j(S) be the shortest distance from node S to destination J, we can express the problem as follows:
f_j with respect to (S) = (minimum nodes in stage j + 1) \times [length of arc SZ + f_{j+1} with respect to (Z)]
Example: Solution
Stage 5: We begin by setting:
f_5 with respect to (J) = 0
Stage 4: Due to the minimal decisions allowed in this stage, we have:
f_4 with respect to (H) = 3 (going to J)
f_4 with respect to (I) = 4 (going to J)
Stage 3: At this stage there are a greater amount of choices we have:
f_3 with respect to (E) = 4 (go to H)
f_3 with respect to (F) = 7 (go to I)
f_3 with respect to (G) = 4 (go to H)
Stage 2: At this stage there are as many choices as there are at stage 3:
f_2 with respect to (B) = 11 (go to E or F)
f_2 with respect to (C) = 7 (go to E)
f_2 with respect to (D) = 8 (go to E or F)
Stage 1: As this is the initial step, there are only two decisions to make:
f_1 with respect to (A) = 11 (go to C or D)
The solution to this problem, and the most efficient method of traversing this course is to follow the path:
A - C - E - H - J
Now that we have tried an example, let's try some problems!
