昨天找出了 Graph 中從 A 到 G 的最短路徑，但如果節點越來越多，光靠人工把所有 Path 都列出來比較，顯然不太實際。
所以今天終於要進入這次 Graph 的主角：Dijkstra's Algorithm（戴克斯特拉演算法）。
Dijkstra 可以從一個起點出發，找出到其他節點的最短距離。簡單來說，它不會一開始就把所有 Path 列出來，而是：
每次挑目前距離起點最近、還沒處理過的節點，再看看經過它之後，能不能讓其他節點的距離變得更短。
今天就用下圖的 Graph，試著從 A 找到 G。
Dijkstra 執行時，我需要記錄：
一開始 A 到自己的距離是 0，其他節點還不知道怎麼到達，所以先設成 ∞。
| 頂點 | Distance | Previous | Visited |
|---|---|---|---|
| A | 0 | null | false |
| B | ∞ | null | false |
| C | ∞ | null | false |
| D | ∞ | null | false |
| E | ∞ | null | false |
| F | ∞ | null | false |
| G | ∞ | null | false |
另外還會需要 Priority Queue（優先佇列），這裡可以先簡單理解成：
讓我每次都能優先拿到目前 Distance 最小的節點。
一開始只有：
[0, A]
先取出 A，它相鄰的節點有 B、C、D：
A → B = 4
A → C = 2
A → D = 7
原本它們的 Distance 都是 ∞，所以更新成：
B：Distance = 4，Previous = A
C：Distance = 2，Previous = A
D：Distance = 7，Previous = A
A 處理完成後，標記成 Visited = true。
這時 Priority Queue 可以想成：
[2, C]
[4, B]
[7, D]
接下來不是按照 A、B、C 的順序處理，而是選擇目前 Distance 最小的 C。
C 相鄰的節點有 A、B、D、F。
A 已經處理完成可以跳過，但 B、D 即使已經有 Distance，還是要重新比較。
例如經過 C 到 B：
A → C → B
2 + 3 = 5
B 原本是 4，因為 5 > 4，所以不更新。
D 也是：
2 + 6 = 8
原本 D 是 7，一樣維持不變。
但走到 F：
2 + 8 = 10
比原本的 ∞ 小，因此更新：
F：Distance = 10
Previous = C
這個「找到更短的距離就更新」的動作，就是 Dijkstra 很重要的 Relaxation（鬆弛）。
接著目前還沒處理的節點中，B 的 Distance 4 最小，所以換 B。
從 B 走到 E：
A → B → E
4 + 1 = 5
因此：
E：Distance = 5
Previous = B
再看看 F：
A → B → F
4 + 5 = 9
F 原本的 Distance 是 10，現在找到 9，代表有更短的走法。
所以再次更新：
Distance：10 → 9
Previous：C → B
這裡也讓我開始理解 Dijkstra 的一個重點：
Distance 不是第一次算出來就固定，而是在節點被正式確定之前，只要找到更短的走法，就會持續更新。
接下來繼續選擇 Distance 最小的節點。
E 的 Distance 是 5，經過 E 到 F：
5 + 2 = 7
因此 F 又從 9 更新成 7：
F：Distance = 7
Previous = E
接著從 F 到 G：
7 + 3 = 10
所以最後：
G：Distance = 10
Previous = F
但 Distance 只告訴我「最短距離是多少」，如果想知道實際經過哪些節點，就要靠一路記錄下來的 Previous。
從 G 往回找：
G ← F ← E ← B ← A
再反過來：
A → B → E → F → G
總距離就是：
4 + 1 + 2 + 3 = 10
所以 Dijkstra 並不是把所有 Path 全部列出來再比較，而是：
選出目前距離起點最近的節點 → 檢查 Neighbor → 找到更短距離就更新 Distance 與 Previous → 再繼續找下一個最近的節點。
昨天我是用眼睛找最短路徑，今天終於開始理解：如果要讓程式自己找，原來需要把 Distance、Previous、Visited 這些狀態一個一個記錄下來。
下一步，就是想辦法把今天手上的這張 Distance Table，真的變成 TypeScript。
本文直接引用一句：
「固定了一個頂點作為源節點然後找到該頂點到圖中所有其它節點的最短路徑，產生一個最短路徑樹。」
來源：Wikipedia〈戴克斯特拉演算法〉
其餘本文內容為依照 Graph 手算流程重新整理，沒有直接引用其他網站文字。
iThome鐵人賽
看影片追技術
看更多