前面認識 Graph 時有提到，Edge 除了表示兩個 Vertex 之間有連接關係之外，還可以加上 Weight（權重），用來表示距離、時間或成本。

但今天遇到的問題是：

如果從 A 到 B 有很多條 Path，我該怎麼知道哪一條才是最好的？

這就是今天要認識的 Shortest Path（最短路徑問題）。

最短路徑，不一定真的是「距離最短」

第一次看到 Shortest Path，我直覺會把它理解成：

找出「距離」最短的路。

但其實這裡的「最短」，更準確來說是找出 Weight 總和最小的 Path。

例如現在從家裡到公司有三條路：

如果 Weight 代表「距離」，第一條可能是最短路徑；但如果 Weight 代表「時間」，第三條反而才是最好的選擇。

所以 Weight 到底代表什麼，要看我們想解決的問題。

它可以是：

• 地圖導航的距離、時間
• 航班的票價
• 網路傳輸的成本
• 遊戲角色移動到某個位置的代價

也就是說，Shortest Path 真正想找的是：

從起點到終點之間，找出 Weight 總和最小的 Path。

「Path 的 Weight 是所有 Edge Weight 的總和」這個概念參考自 Chiu CC 的〈Shortest Path：Intro〉。

Edge 少，不代表成本比較低

假設現在有：

A --10--> B

A --3--> C --2--> B

從 A 直接走到 B，只經過一條 Edge：

A → B = 10

但如果繞去 C：

A → C → B
= 3 + 2
= 5

雖然第二條 Path 經過更多 Edge，Weight 總和反而比較小。

所以 Shortest Path 並不是在找「經過最少 Vertex」或「Edge 最少」的路，而是要比較整條 Path 的 Weight 總和。

「Edge 較少的 Path，不一定具有較小的 Weight」這個觀念參考自 Chiu CC 的〈Shortest Path：Intro〉。

最短路徑有哪些演算法？

查資料時才發現，解決 Shortest Path 的方法其實很多，例如：

這篇先知道它們是「不同情況下的不同工具」就好，暫時不深入研究每一種演算法。

因為接下來我的目標，是先從其中一個開始：

Dijkstra Algorithm。

明天開始找最短路徑

今天先不急著寫演算法，而是先搞懂 Shortest Path 到底想解決什麼問題。

目前我把它理解成：

在 Graph 中，從起點到終點可能存在很多條 Path，而 Shortest Path 要找的是其中 Weight 總和最小的那一條。

但新的問題也跟著出現了。

如果 Graph 只有幾個 Vertex，我還可以自己把每條 Path 的 Weight 加起來比較；但如果今天有幾百、幾千個 Vertex，總不能把所有路線全部列出來吧？

那 Dijkstra 到底怎麼知道下一步該往哪裡走？

下一章就來正式認識 Dijkstra Algorithm。

參考資料

Chiu CC，〈Graph: Intro（簡介）〉
https://alrightchiu.github.io/SecondRound/graph-introjian-jie.html

Sbooker，〈最短路徑問題，有哪些演算法？〉
https://www.sbooker.com/2024/02/17/%E6%9C%80%E7%9F%AD%E8%B7%AF%E5%BE%91%E5%95%8F%E9%A1%8C%EF%BC%8C%E6%9C%89%E5%93%AA%E4%BA%9B%E6%BC%94%E7%AE%97%E6%B3%95%EF%BC%9F/