首頁‎ > ‎

公車路網成本最佳化:最小生成樹

背景

某家公車路網如下圖:

資料安排

1 2 3 4 5 6
1 10 30 45
2 50 40 25
3 35 15
4 20
5 55

演算法說明

  1. 在 列 (1) 中,找該列最小路徑 = P(1, 2) = 10
  2. 在 列 (2) 中,找該列最小路徑 = P(2, 6) = 25
  3. 在 列 (3) 中,找該列最小路徑 = P(3, 6) = 15
  4. 在 列 (4) 中,找該列最小路徑 = P(4, 6) = 20
  5. 在 列 (5) 中,找該列最小路徑 = P(5, 6) = 55
  6. 在 行 (5) 中,找該行最小路徑 = P(5, 3) = 35
  7. 因為 節點 5 相關路徑中,P(5, 3) 最小,故刪除 P(5, 6)
  8. 總成本 = P(1, 2) + P(2, 6) + P(3, 6) + P(4, 6) + P(5, 3)

解答