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

背景：

某家公車路網如下圖：

演算法說明：

• 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)