|
背景：
某家公車路網如下圖：
|
資料安排：
|
|
1 |
2 |
3 |
4 |
5 |
6 |
| 1 |
|
10 |
|
30 |
45 |
|
| 2 |
|
|
50 |
|
40 |
25 |
| 3 |
|
|
|
|
35 |
15 |
| 4 |
|
|
|
|
|
20 |
| 5 |
|
|
|
|
|
55 |
|
|
演算法說明：
- 在 列 (1) 中，找該列最小路徑 = P(1, 2) = 10
- 在 列 (2) 中，找該列最小路徑 = P(2, 6) = 25
- 在 列 (3) 中，找該列最小路徑 = P(3, 6) = 15
- 在 列 (4) 中，找該列最小路徑 = P(4, 6) = 20
- 在 列 (5) 中，找該列最小路徑 = P(5, 6) = 55
- 在 行 (5) 中，找該行最小路徑 = P(5, 3) = 35
- 因為 節點 5 相關路徑中，P(5, 3) 最小，故刪除 P(5, 6)
- 總成本 = P(1, 2) + P(2, 6) + P(3, 6) + P(4, 6) + P(5, 3)
|
解答：
|
|
|