Path

• Path是指在Graph中任意選擇起點跟終點，找出不重複的邊與頂點，將兩個點連通形成一條連續邊。路徑的邊上也可能會有權重。
• Short path 就是Graph中所有可能連通起點連到終點的path中，加權值最小的path。
  • 不一定會是邊最少的或是點最少的Path。

我們可以將圖的頂點想像成我們要去的景點，邊是通往這幾個景點的道路，其加權值就是需要花費的交通時間，我們每個景點都一定要去，就要找一條Short Path，讓我們以最少的時間就能將每個景點都玩遍。

• Short Path Algorithm類型 :

1. Single Source Shortest Paths
   一 -> 全
   選擇一個起點，找出起點到圖上其餘每一點的最短距離。
   EX: Dijkstra's Algorithm
2. All Pairs Shortest Paths
   全 -> 全
   求出圖上所有頂點兩兩之間的最短距離。
   EX:Floyd Algorithm

Dijkstra's Algorithm

Dijkstra提出了計算從某一個起點到其餘各點的Short Path的演算法 - Dijkstra's Algorithm

以最短路徑遞增的順序，一個一個決定頂點的最短路徑。
凡是最短路徑已經決定的頂點，可以幫助我們更新其餘未決定頂點的已知最短路徑。

• 例子明天補上。

參考

細談資料結構 第六版
ISBN 978-986-312-014-8