上一篇我們討論 BFS 時，用了一個很適合它的問題：

從 A 到 F，最少要經過幾個站？

只要每經過一個站，都把它看成相同的一步，BFS 就能一層一層往外搜尋，第一次到達目的地時，就得到「最少步數」。

例如：

A → B → D → F

如果總共經過 3 條 Edge，那麼我們可以得出結論：

A 到 F 的最少步數是 3

這時 Graph 裡的每一條 Edge，其實都被默認成一樣的成本：

A → B = 1
B → D = 1
D → F = 1

但現實世界的導航通常不是這樣。
今天我們把問題稍微改一下：

從 A 到 F，怎麼走最快？

看起來只改了一點點，問題的性質就開始不一樣了。

最少經過幾站，不一定最快到達

假設現在有這樣一張交通網路：

如果只看經過幾條 Edge：

A → B → F

只需要 2 步。
而：

A → C → D → E → F

需要 4 步。
如果使用上一篇的 BFS，我們很自然會先找到：

A → B → F

因為它經過的 Edge 比較少。
但現在幫每條路加上實際需要的時間：

這時再算一次。
第一條路：

A → B → F

10 + 20 = 30 分鐘

第二條路：

A → C → D → E → F

3 + 3 + 3 + 3 = 12 分鐘

結果完全相反了。

經過比較少站的路：
A → B → F
30 分鐘

經過比較多站的路：
A → C → D → E → F
12 分鐘

所以：

最少步數，不等於最少時間

這也是為什麼導航問題不能永遠只靠 BFS。

問題改變的地方在哪裡？

上一篇的 Graph 可以想成每走一條 Edge 成本都是 1。
所以我們只需要比較：走了幾條 Edge？

但現在不一樣，每一條 Edge 都有自己的成本：

A → B = 10
A → C = 3
C → D = 3
...

這種 Graph 稱為：

Weighted Graph

也就是：

每一條 Edge 不只是表示「兩個 Node 之間有連接」，還帶有某種數值。

這個數值稱為：

Edge Weight

例如在導航問題裡，Weight 可以表示行駛時間，所以：

A → B = 10

可以理解成：

從 A 到 B 需要 10 分鐘

Weight 不一定是距離

看到 Weighted Graph，很容易先想到：

Weight = 距離

但這只是其中一種可能。
例如一條道路可以有：

距離：5 公里
時間：12 分鐘
過路費：30 元

那麼同一條 Edge，其實可以被賦予不同意義。
如果今天我們問：

哪條路距離最短？

那麼 Weight 可以是公里數。

如果問題變成：

哪條路最快？

Weight 可以是分鐘。

如果問題變成：

哪條路最省錢？

Weight 又可能是費用。

也就是說，Graph 的結構可能完全相同，但我們真正要最佳化的東西不同。

我們開始不只是數「走幾步」

在 BFS 裡，我們可以把搜尋想成：

距離 A 1 步的 Node
↓
距離 A 2 步的 Node
↓
距離 A 3 步的 Node

因為每一步成本相同，所以「走了幾步」本身就是我們要比較的東西。
但 Weighted Graph 裡可能出現：

A → B
cost = 10

以及：

A → C → D
cost = 3 + 3 = 6

雖然：

A → B

只走了一步，但：

A → C → D

走了兩步，累積成本反而比較低。
所以這時搜尋策略不能再只是：

誰離起點的 Edge 數量比較少？

而要改成：

目前已知的路徑中，誰的累積成本最低？

從 Queue 到「目前最便宜的選擇」

前面 BFS 使用 Queue，因為 BFS 的規則是 先被發現→ 先被處理。
更精準地說，它按照搜尋的 level 一層一層往外擴張。

但現在如果 Edge Weight 不同，我們想優先處理的就不再是最早進 Queue 的 Node，而是目前累積成本最低的 Node。

假設從 A 出發：

A → B = 10
A → C = 3

那我們目前知道：

到 B 的成本 = 10
到 C 的成本 = 3

此時比起 B，我們應該優先繼續探索 C。
因為目前看來 C 比較便宜，這開始讓我們想起前面 Day 3 的 Priority Queue。

• 普通 Queue 關心：誰先進來？
• Priority Queue 關心：誰的 priority 比較高？

而在這裡，我們可以把 priority 想成：

目前累積成本越小
→ 越優先處理

所以整個結構開始變成：

Weighted Graph + Priority Queue
↓
Dijkstra

Dijkstra 在做什麼？

這裡先不急著背完整程式碼，先建立它最重要的直覺。
假設從 A 出發：

A → B = 10
A → C = 3

一開始：

A = 0
B = ∞
C = ∞

∞ 可以先理解成：

我們還不知道怎麼到那裡

從 A 出發之後，我們找到：

B = 10
C = 3

現在已知成本最低的是：

C = 3

所以先探索 C。
假設：

C → D = 3

那麼：

到 D 的成本
= 到 C 的成本 + C → D

= 3 + 3
= 6

因此現在可能變成：

B = 10
D = 6

接下來優先處理誰？

不是比較誰比較早被發現。
而是比較：

D = 6
B = 10

所以先處理 D。
這就是 Dijkstra 最核心的搜尋直覺：

每一次，都先處理目前已知累積成本最低的位置

走到這裡要多少成本？

可以把每個 Node 想成記錄一個問題：

目前已知從起點走到這裡，最少需要多少成本？

例如：

A = 0
C = 3
D = 6
E = 9
F = 12

如果另一條路又發現 A → B → F，而它的成本是：

10 + 20 = 30

我們就可以比較：

目前已知 F = 12

新路徑 F = 30

30 並沒有比較好，所以不需要更新。
但如果新找到一條：

cost = 8

那就代表：

原本：
F = 12

現在：
F = 8

我們找到了一條更便宜的路。
這個「發現更低成本，就更新目前最佳答案」的動作，在最短路徑演算法裡非常重要。
通常會稱作：

relaxation

這個名詞現在先認得即可，不需要急著深入它的數學定義。

為什麼 BFS 不需要做這麼多事？

因為在上一篇的問題裡，每條 Edge 的成本都一樣。
例如全部都是 cost = 1，那麼：

走 2 條 Edge
一定比走 3 條 Edge 成本低

因為：

2 × 1 < 3 × 1

所以 BFS 只要按照 level 搜尋：

1 步
2 步
3 步

就已經等於：

cost = 1
cost = 2
cost = 3

但現在：

Edge A = 20
Edge B = 3
Edge C = 3

走一條 Edge：

cost = 20

可能反而比走兩條：

3 + 3 = 6

還昂貴，所以：

當每一步的成本不再相同，「步數」就不再足以代表路徑好壞

所謂「最短路徑」，到底短的是什麼？

這裡有一個很容易產生誤解的詞：

Shortest Path

我們通常翻成：

最短路徑

但「最短」不一定真的指物理距離。
假設有三條路：

路線 A
距離：5 km
時間：30 分鐘
費用：0 元

路線 B
距離：8 km
時間：15 分鐘
費用：100 元

路線 C
距離：10 km
時間：20 分鐘
費用：20 元

那哪一條才是「最短路徑」？

答案取決於你問的是什麼。

• 如果目標是距離最短：答案可能是 A。
• 如果目標是時間最短：答案可能是 B。
• 如果目標是費用最低：答案可能又是 A。

所以真正重要的其實不是「Shortest」這個詞。

是去思考：

我們到底想最小化什麼？

從資料結構開始走向「目標」

前面幾天，我們一直在問：

• 資料怎麼表示？
• 下一個要處理誰？
• 要怎麼搜尋？

但從 Weighted Graph 開始，另一個問題會變得越來越重要：

什麼才算是比較好的答案？

假設導航系統有兩條路：

路線 A
15 分鐘
100 元

路線 B
20 分鐘
0 元

哪一條比較好？

其實沒有辦法只靠 Graph 自己回答。
因為 Graph 只負責描述：

• 有哪些地方
• 哪些地方互相連接
• 每條連接有哪些成本

真正決定答案的，是我們對「好」的定義。
例如：

• minimize(time) 代表：我要時間最少
• minimize(cost) 代表：我要花費最低
• 也可能是某種組合 minimize(time + toll)

這種「我們到底要最佳化什麼」的描述，可以開始把它理解成：

Objective Function 目標函式

現在不需要學它正式的數學形式。
先記住一個簡單的理解：

Algorithm 不知道什麼叫「最好」。

你必須先告訴它：
你想讓什麼東西變小，
或者讓什麼東西變大。

同一張 Graph，可以得到完全不同的答案

例如同一個交通網路：

A → B → F
A → C → D → F

每條 Edge 同時可能包含：

{
  distance: 5,
  time: 10,
  price: 30
}

如果你問：哪條路 distance 最低？
會得到一個答案。

問：哪條路 time 最低？
可能得到另一個答案。

再問：哪條路 price 最低？
答案又可能不同。

Graph 沒有變過，變的是我們如何定義成本。
而一旦成本的定義改變，搜尋出來的「最佳路徑」也可能跟著改變。

回頭看 BFS 與 Dijkstra

現在可以重新整理這兩種搜尋方式的差異。
BFS 適合的情況可以想成每條 Edge 成本相同，所以導出：

最少 Edge 數 = 最低總成本

而 Dijkstra 處理的是每條 Edge 有不同的非負成本，因此我們必須追蹤累積成本，
並優先探索目前已知成本最低的路徑。
所以可以先建立這樣的直覺：

Unweighted Graph + Queue
→ BFS

以及：

Weighted Graph + Priority Queue
→ Dijkstra

這並不是說只要看到 Weighted Graph 就永遠使用 Dijkstra。
之後我們還會遇到更多限制與不同演算法。
但至少現在可以看出：

問題一旦加入「不同成本」，搜尋策略也必須跟著改變

今天真正重要的不是記住 Dijkstra

如果只記住：

• BFS → Queue
• Dijkstra → Priority Queue

還是有點片面，更重要的是理解它們背後的問題差異。
BFS 回答的是：

如果每一步成本相同，怎麼找到最少步數？

Dijkstra 開始回答：

如果每一步成本不同，怎麼找到累積成本最低的路徑？

而再往下一層，其實還有一個更重要的問題：

這個成本到底代表什麼？

因為現實世界中的「最好」很少只有一種定義。
導航可以追求距離最短，也可以追求時間最短，甚至花費最低。
真正開始設計演算法以前，我們往往必須先回答：

我們真正想最佳化的是什麼？

小結：從「可以走到」變成「必須先做」

回頭看這幾篇文章，我們從一張捷運路網開始，依序回答了：

Graph 描述什麼關係？
↓
Graph 在程式裡怎麼保存？
↓
怎麼走過一張 Graph？
↓
不同搜尋順序有什麼差異？
↓
Edge 有不同成本時，怎麼找最低成本？

到目前為止，Edge 主要代表可以從 A 走到 B，但現實世界還有另一種很常見的關係：

A 必須完成
↓
B 才能開始

例如：

• 先修課程 → 後續進階課程
• 備料完成 → 開始烹煮
• 安裝 dependency → 啟動應用程式

這時 Edge 描述的就不只是「彼此相連」，而是不能隨意顛倒的先後關係。
所以下一章要問的是：

如果 B 必須等 A 完成才能開始，我們該怎麼描述這種帶有方向的關係？