5.3 最短路徑與 Dijkstra 演算法

動機

最短路徑問題尋找的是一條路線，而不只是判斷兩點是否連通。固定來源頂點 s 後，我們希望對每個可到達的頂點 v，找出由 s 到 v 的最小邊權重總和；這就是單一來源最短路徑問題。

第一條被發現的路徑未必最短。例如，一條權重為 9 的直接邊，後來可能被權重分別為 3 和 2 的兩條邊取代。 Dijkstra 演算法因此先保存暫定估計，透過鬆弛逐步改善，再按照有證明保證的次序把頂點確定下來。

適用條件——所有邊權重必須非負。 Dijkstra 的貪心確定步驟只有在每條邊的權重都至少為零時才正確。 零權重邊可以使用；負權重邊不可以。圖中只要出現一條負權重邊，便應改用其他最短路徑方法。

這不是可省略的技術細節。下文會用只有三個頂點、沒有負環的例子，直接展示一條負邊如何令已確定的答案變錯。

定義

設 G=(V,E) 是有向或無向圖，來源為 s，而每條邊 (u,v) 的權重滿足 w(u,v)\ge 0。一條路徑的成本是沿途 所有邊權重的總和。以 delta(s,v) 表示由 s 到 v 的真正最短距離；若 v 不可到達，距離記作無窮大。

定義

暫定距離與前驅

d[v] 是目前已找到的 s 到 v 路徑中最小的成本，所以它是真正最短距離 delta(s,v) 的上界。 pred[v] 記錄實現目前 d[v] 的路徑上，緊接在 v 之前的頂點。

初始化為

$$d[s]=0,\qquad d[v]=\infty\quad(v\ne s),$$

而所有前驅均未定義。找到更佳路徑時，距離與前驅必須同步更新。

定義

邊的鬆弛

鬆弛邊 (u,v) 時，把舊估計 d[v] 與經過 u 延伸而來的候選值比較：

$$\operatorname{candidate}=d[u]+w(u,v).$$

若候選值嚴格較小，便設定

$$d[v]\leftarrow d[u]+w(u,v),\qquad \operatorname{pred}[v]\leftarrow u.$$

否則兩項都保持不變。

已確定集合 S 保存最短距離已獲證明的頂點。每一輪從尚未確定的頂點中選出 d 最小者，加入 S，再鬆弛 它的所有出邊。若最小值相同，可以任意打破平手；前驅樹可能不同，但最終距離不變。

Dijkstra(G, s):
  對每個頂點 v:
    d[v] = infinity
    pred[v] = undefined
  d[s] = 0
  S = empty set

  當仍有暫定距離有限的未確定頂點:
    u = 暫定距離最小的未確定頂點
    把 u 加入 S
    對每條出邊 (u, v)，其中 v 不在 S:
      candidate = d[u] + w(u, v)
      若 candidate 小於 d[v]:
        d[v] = candidate
        pred[v] = u

演算法結束後，由目標沿 pred 反向走至 s，再把次序倒轉，便可重建路徑。仍為無窮大的頂點不可由 s 到達， 也沒有可重建的前驅鏈。

定理 / 命題

定理

有限估計是實際路徑成本及上界

在演算法任何時刻，每個有限的 d[v] 都對應一條實際找到的 s 到 v 路徑。因此

$$d[v]\ge \delta(s,v).$$

鬆弛只會令估計下降，而且不會破壞此上界性質。

定理

非負權重下的安全確定步驟

若所有邊權重非負，當 Dijkstra 選出暫定距離最小的未確定頂點 u 時，

$$d[u]=\delta(s,u).$$

所以 u 的距離可以永久確定，往後無須重新打開。

定理

前驅鏈重建最短路徑

演算法結束後，從任何可到達頂點 v 沿前驅返回 s，所得路徑的成本是 d[v]，亦即最短路徑成本。 若有多條同成本最短路徑，前驅只會記錄其中一條。

證明思路

先看上界。初始化的 d[s]=0 代表空路徑；其後每個有限估計，都是把一條已由 d[u] 表示的實際路徑接上 (u,v) 而得。因此 d[v] 不可能低於所有可行路徑中的最小值。

再證明貪心選擇。假設所有已確定頂點的距離都正確，u 是現在暫定距離最小的未確定頂點。取一條 s 到 u 的最短路徑，令 y 是路徑上第一個未確定頂點，x 是它之前的已確定頂點。當 x 被確定時，邊 (x,y) 已被 鬆弛，所以結合上界性質可得

$$d[y]=\delta(s,y).$$

由 y 到 u 的餘下邊全部非負，故 delta(s,y)\le delta(s,u)。另一方面，u 是最小暫定值，於是

$$\delta(s,u)\le d[u]\le d[y] =\delta(s,y)\le\delta(s,u).$$

四者只可能全部相等，因此 d[u]=delta(s,u)。若餘下路段包含負邊，delta(s,y)\le delta(s,u) 這一步便可能失效； 這正是非負條件不可缺少的原因。

例題詳解

例題

一次鬆弛要同時更新兩項資料

假設 d[u]=7、w(u,v)=4，而原來 d[v]=14、pred[v]=x。經 u 的候選成本為

$$7+4=11\lt14.$$

所以更新為 d[v]=11 及 pred[v]=u。若原來 d[v]=10，則兩者都不改。只改距離而不改前驅，會令最後輸出的 數值與重建路徑互相矛盾。

例題

由 v0 出發的完整最短路徑追蹤

考慮以下有向帶權邊：

v0->v1(3)、v0->v2(2)、v0->v3(6)、v0->v4(4)、 v1->v3(5)、v1->v5(5)、v2->v4(1)、v4->v3(2)、 v4->v5(4)、v3->v5(1)。

表內括號中的頂點是前驅，破折號表示未定義。確定 v2 後，v1 和 v4 的暫定距離同為 3；以下在這兩個同為最小值的頂點中 先選 v1。

階段	本輪選擇	選擇後的已確定集合	d[v0]	d[v1]	d[v2]	d[v3]	d[v4]	d[v5]
初始	—	{}	0 (—)	infinity (—)	infinity (—)	infinity (—)	infinity (—)	infinity (—)
鬆弛 v0 的出邊	v0	{v0}	0 (—)	3 (v0)	2 (v0)	6 (v0)	4 (v0)	infinity (—)
鬆弛 v2 的出邊	v2	{v0,v2}	0 (—)	3 (v0)	2 (v0)	6 (v0)	3 (v2)	infinity (—)
鬆弛 v1 的出邊	v1	{v0,v2,v1}	0 (—)	3 (v0)	2 (v0)	6 (v0)	3 (v2)	8 (v1)
鬆弛 v4 的出邊	v4	{v0,v2,v1,v4}	0 (—)	3 (v0)	2 (v0)	5 (v4)	3 (v2)	7 (v4)
鬆弛 v3 的出邊	v3	{v0,v2,v1,v4,v3}	0 (—)	3 (v0)	2 (v0)	5 (v4)	3 (v2)	6 (v3)
在 v5 完成	v5	{v0,v2,v1,v4,v3,v5}	0 (—)	3 (v0)	2 (v0)	5 (v4)	3 (v2)	6 (v3)

最終距離依次為 0,3,2,5,3,6。例如前驅鏈

$$v_5\leftarrow v_3\leftarrow v_4\leftarrow v_2\leftarrow v_0$$

倒轉後得到 v0 -> v2 -> v4 -> v3 -> v5，成本為 2+1+2+1=6。v5 的估計先後由無窮大改善至 8、 7、6，清楚說明「已發現」不等於「已確定」。

例題

只有一條負邊的最小反例

考慮有向圖 s->u(1)、s->v(2)、v->u(-2)。鬆弛 s 的出邊後，d[u]=1 而 d[v]=2，所以 Dijkstra 會先確定 u。然而路徑 s->v->u 的成本是 2+(-2)=0，才是真正最短答案。稍後處理 v 時，演算法需要改善一個 已宣告為最終答案的頂點。此圖沒有負環；單是一條負邊已足以破壞貪心確定論證。

例題

明確說明點權轉邊權的帶權網格

在以下 3 乘 4 點權網格中，求由左上角到右下角的最小成本路徑；N 表示不可進入：

	第 1 欄	第 2 欄	第 3 欄	第 4 欄
第 1 列	1	2	5	1
第 2 列	4	1	N	N
第 3 列	1	2	1	1

每個可進入方格建立一個頂點。本題只容許向右或向下走一步；目的地越界或為 N 時不建立該邊。網格把成本 放在頂點，Dijkstra 則讀取邊權，所以必須先固定轉換規則：

$$w\bigl((i,j),(i',j')\bigr)=M[i'][j'], \qquad d[(1,1)]=M[1][1]=1.$$

即每條邊收取「進入目的方格」的成本，而初始化另把起點成本計算一次。到右下角的最短路徑為

$$(1,1)\to(1,2)\to(2,2)\to(3,2)\to(3,3)\to(3,4),$$

總點權是

$$1+2+1+2+1+1=8.$$

沿第一欄向下的另一條路以成本 8 到達 (3,2)，選定路線則以成本 6 到達；兩者再走相同後段，總成本分別為 10 和 8。經 (1,3) 的上方分支不能向下，因為 (2,3) 和 (2,4) 都是障礙。若把起點初始化為零，選定路線 的邊權總和是 7；最後加回起點權重仍得到 8。若混用兩種約定，答案便會出現漏算一個方格的錯誤。

若以鄰接矩陣儲存圖，並線性掃描下一個最小值，時間是 O(V^2)。若以鄰接表配合由二元堆實作的最小優先佇列， 至多 V 次 extract-min 加上至多 E 次優先值更新，時間為

$$O((V+E)\log V),$$

空間為 O(V+E)。在只可向右或向下的 n 乘 m 網格中，V\le nm、E\le 2nm-n-m；障礙只會減少數目， 所以二元堆實作的時間為 O(nm log(nm))。

實作時，確定頂點的時機同樣重要：頂點在以最小值由優先佇列取出時才確定，第一次加入佇列只代表找到暫定路徑， 其後仍可能被鬆弛改善。若程式不用 decrease-key，而是每次改善都插入新項目，取出時便要丟棄鍵值已不等於 d[v] 的舊項目。若餘下最小鍵值已是無窮大，所有未確定頂點均不可由 s 到達，演算法可直接停止，不應虛構前驅。

常見錯誤

常見錯誤

有負邊仍使用 Dijkstra

只檢查有沒有負環並不足夠。標準 Dijkstra 要求每條邊都非負，即使圖中完全沒有負環亦一樣。

常見錯誤

把已發現當成已確定

有限估計只代表已找到一條路；頂點必須成為最小未確定者並被取出，距離才是最終值。完整追蹤例中 v5 的三次改善正好 顯示兩者差別。

常見錯誤

只更新距離而漏掉前驅

每次嚴格改善都要同步更新 d[v] 和 pred[v]，否則最後顯示的成本與重建路徑可能來自不同路線。

常見錯誤

混淆 BFS、Dijkstra 與 MST

BFS 在無權圖或所有邊同成本時最小化邊數；Dijkstra 最小化非負總權重；MST 最小化連接所有頂點的樹之總邊權， 並不保證由某個來源出發的每條路都最短。

常見錯誤

沒有交代網格成本約定

若數字寫在方格，必須說明成本在進入還是離開方格時支付，以及有沒有計算起點。約定未定，路徑總值便不可核對。

總結

• d[v] 是暫定上界，pred[v] 記錄實現該上界的路線。
• 鬆弛檢查經 u 延伸是否可以改善 v，成功時同時更新距離及前驅。
• 所有邊非負時，最小未確定估計可以安全成為最終答案；零權邊可用，負權邊不可用。
• BFS 適合無權最短路徑；Dijkstra 處理不相等的非負權重；MST 解答的是另一個總連接成本問題。
• 鄰接矩陣配線性選擇為 O(V^2)；鄰接表配二元堆為 O((V+E) log V)。

練習

思考檢查

一次成功鬆弛後，哪兩項資料必須改變？

分別指出數值記錄及用來重建路徑的記錄。

1. 已知 d[a]=4、w(a,b)=6、d[b]=13、pred[b]=x，鬆弛 (a,b)。若原來 d[b]=9，答案又如何？
2. 利用完整追蹤表，重建 v0 至 v3 和 v5 的最短路徑，並用邊權核對成本。
3. 在 s->u(1)、s->v(2)、v->u(-2) 中，安全確定證明的哪一步失效？
4. 一個無權圖以鄰接表表示，應選哪個最短路徑演算法？時間複雜度是多少？
5. 按上文網格約定，(3,2) 的估計是多少？比較例中討論的到達該方格的兩條路線。
6. 各寫出 BFS 最短路徑、Dijkstra 最短路徑及最小生成樹目標的一項差別。

答案與解答

解答 · 快速檢查答案

成功鬆弛會把 d[v] 改為較小候選值，並把 pred[v] 改為產生該候選值的頂點。

解答 · 引導解答

1. 候選值是 4+6=10。由 13 更新為 d[b]=10、pred[b]=a；若舊值為 9，因為 10 不較小，完全不改。
2. v3 ← v4 ← v2 ← v0 倒轉為 v0->v2->v4->v3，成本 2+1+2=5。到 v5 再接 v3->v5(1)，總成本為 6。
3. 證明曾用「由 y 到 u 的餘下路段非負」，從而推出 $\delta(s,y)\le\delta(s,u)$。負邊 v->u 令此不等式 失去保證，較大的前段成本反而可在稍後產生較小總成本。
4. 使用 BFS；其佇列按邊數層次探索，鄰接表實作需 O(V+E) 時間。
5. (3,2) 的估計為 1+2+1+2=6，路徑是 (1,1)->(1,2)->(2,2)->(3,2)。 另一條 (1,1)->(2,1)->(3,1)->(3,2) 成本為 1+4+1+2=8，所以鬆弛保留 6。
6. BFS 在無權圖最小化邊數；Dijkstra 由一個來源最小化非負路徑總權重；MST 則最小化連接全圖的生成樹總權重。