優先隊列本身不決定鍵值的意義。Dijkstra 算法按來源出發的暫定路徑長度排序;Prim 算法則按生長中樹的邊界跨越邊排序。兩者都可用最小堆,但不變量和目標不同。本章以圖追蹤數據結構,包括過時堆項和父指標。
圖與優先隊列的表示
無向加權圖由頂點及加權邊組成。鄰接表為每個頂點儲存鄰點及邊權;每條無向邊分別出現在兩端的表中。最小堆按指定優先值儲存項目,並返回最小項,但其底層陣列並非排序序列。若平局影響追蹤,可指定頂點名稱等確定性的次要鍵;否則可能有多個正確軌跡。
定義 14.2.1
(暫定距離、定案與鬆弛)
對 Dijkstra,dist[v] 是目前已發現的來源至 路徑中的最短長度,尚未必是真正最短距離;父指標記錄一條達到此暫定值的路徑。起初來源距離為零,其餘為無窮大。取出當前暫定距離最小且未定案的頂點,將其定案,再檢查其出邊。對 的鬆弛是比較 dist[u]+w(u,v) 與 dist[v];嚴格改善時替換距離及父節點。本章平局保留原來的父節點。
定義 14.2.2
(惰性堆項與過時項)
堆可支援 decrease-key 以修改既有項。惰性實作則每次嚴格改善便推入新數對,舊項留在堆內;取出時若頂點已定案或項目的值不等於當前距離,便丟棄。若不檢查,過時項可能被誤當成新工作。無窮大是概念上的初始標籤;實作可以等到發現有限候選值才把頂點入堆。
例題:惰性堆最短路徑
例題 14.2.3
(五個頂點上的惰性堆最短路徑)
頂點為 A,B,C,D,E,無向邊為 AB:2, AC:3, BC:1, BD:3, CD:1, CE:5, DE:2。由 A 出發,堆數對先按距離、再按字母排序;只在嚴格改善時更新。寫出距離、父節點及每次定案後的堆。以下列出的是按優先值排序的堆內容,並非說堆的底層陣列已排序。
起初為 [(0,A)]。取出 A 並定案,鬆弛 A–B、A–C 後堆為 [(2,B),(3,C)],B、C 的父均為 A。取出 B,距離為 2;經 B 到 C 長度為 3,與現值相同,故依平局規則保留父 A。B–D 給出 5;堆為 [(3,C),(5,D)]。
取出距離 3 的 C。C–D 給出 4,將 D 從 5 改善為 4 並把父改為 C;C–E 給出 8。堆變為 [(4,D),(5,D),(8,E)]。取出距離 4 的 D,鬆弛 D–E,把 E 改善為 6、父改為 D;堆為 [(5,D),(6,E),(8,E)]。彈出 (5,D) 並丟棄:D 已定案,該項過時。取出距離 6 的 E,最後丟棄過時的 (8,E)。
定案距離是 A:0、B:2、C:3、D:4、E:6;父邊為 AB, AC, CD, DE。若另一一致規則在相等時替換父節點,C 也可由 B 到達,長度仍為 3。距離和所選最短路徑樹的身分是不同輸出。這棵樹的邊權和為 8,但 Dijkstra 最小化各頂點的來源路徑長度,不是此總和。
常見錯誤
(未檢查過時就相信彈出的數對)
在追蹤中,(5,D) 在 D 已以距離 4 定案之後才被彈出。若實作把彈出的鍵值指派給頂點,就會把 dist[D]=4 覆寫成 5;若再鬆弛一次 D 的出邊,則是以錯誤的標籤重複工作。除非頂點未定案且鍵值等於當前標籤,否則彈出的數對必須丟棄。
概念視角幾何
把距離看成火焰到達的時間
把每條邊換成長度等於其權的線段,並在時刻 點燃源點。火焰以單位速度蔓延,到達頂點 的時間就是 ,即測地距離;Dijkstra 按火焰到達的次序定案各頂點:最小的暫定標籤,就是火焰下一個到達的頂點。在追蹤中,火焰在 到達 A,在 到達 B,在 到達 C(沿 AC 或 ABC 皆然),在 到達 D,在 到達 E。負權相當於倒著燒的引線,所以非負條件並非技術細節。
為何可以定案
定理 14.2.4
(取出暫定標籤最小的頂點來定案是安全的)
設所有邊權均非負,且每個已定案頂點都已帶有來源至它的真正最短路徑距離。若 是未定案頂點,其暫定標籤有限,並且在未定案頂點中最小,則 就是來源至 的真正距離。因此 Dijkstra 算法為每個可達頂點定案時,所用的都是真正距離。
證明
(較短路徑會暴露一個標籤更小的未定案頂點)
設未定案頂點 的暫定標籤最小,卻有較短的來源至 路徑。沿該路徑取第一個未定案頂點 及其已定案前驅 。 定案時已鬆弛邊 ;若已定案的 標籤正確, 的暫定標籤至多是該路徑至 的前綴長度。剩餘邊權非負,所以前綴不長於整條假定的較短路徑;於是 dist[y] 會小於 dist[u],與選擇 矛盾;若 ,這立即給出 dist[u] < dist[u]。從來源開始歸納即可。若沒有有限的未定案標籤,未發現頂點便不可由來源到達。
證明透視
三個假設,各用一次
這些假設按固定次序出現。歸納假設,即已定案標籤是真正距離,給出 路徑至 的前綴長度;由於 定案時已鬆弛邊 ,便有 至 的前綴長度。非負邊權只用一次,用來由這個前綴過渡到整條假定的較短路徑。最後, 的標籤最小,使 成為矛盾。
去掉非負假設,只有中間一步會失效。在下面的例子中,前綴 AC 的長度為 5,而整條路徑 ACB 的長度只有 1。
非負假設確實重要。
反例模式
負邊會破壞定案規則
對有向邊 權 2、 權 5、 權 −4,按最小標籤定案會先以 2 定案 B,再處理距離 5 的 C;但 長度為 1。圖中根本沒有有向環,因此失敗不是由負環造成。定案後再鬆弛 B,不能修復一個把定案標籤視作最終值的實作;輸入有負邊時須選用假設允許負邊的算法。
Prim 的前沿表示割,而非路徑
定義 14.2.5
(Prim 算法的前沿與過時邊)
Prim 維持已入樹的連通頂點集 。前沿包含一端在 、另一端在外的邊;選最小跨割邊,加入其外端及該邊,再更新前沿。實作可在頂點入 時將邊推進堆;取出邊後若兩端都已在內,便丟棄。這與 Dijkstra 比較距離標籤的過時項條件不同。
引理 14.2.6
(安全邊引理)
設 是連通無向加權圖。設邊集 包含於某棵最小生成樹 ,並設割 沒有被 的邊跨越。若 是此割的一條最輕跨割邊,則存在一棵最小生成樹包含 。
證明
(交換一條跨割邊)
若 已在 中,無須交換;否則加入 形成環,環上另有一條跨越同一割的邊。因沒有 的邊跨割,被替換的邊不屬於 。以 替換它可保留 ,仍是生成樹且權重不增加,故所得樹亦最小。
證明透視
割的條件如何保護交換步驟
每項假設各用一次。 提供一棵可供修改的最小樹。加入 後形成的圈穿過割的次數必為偶數,所以圈上還有另一條跨割邊 ;「 中沒有邊跨過這個割」這項假設,保證 ,因此刪去 後 仍然保留。關鍵一步是這次交換,而不是重新建一棵樹。最後, 最輕給出 ,所以總權不會增加。若容許 跨過割, 就可能屬於 ,交換便會把它破壞。
在 Prim 中,已選邊都位於 內,故當前割符合此條件;引理在每次選擇後保持不變量。允許平局,不同選擇可能得到不同最小樹。
反例模式
割不可跨過已選的邊
聲稱:若 含於某棵最小生成樹,則任何割上最輕的跨割邊都能擴充 ;「 不跨過該割」這個條件是多餘的。取邊 AB:2, AC:2, BC:1,(含於權為 的最小樹 ),以及把 與 分開的割。AB 與 AC 都是最輕的跨割邊,而 本身就跨過這個割。選 得到權為 的 ,它不含於任何最小樹。若取尊重 的割,例如把 與 分開,最輕的跨割邊是 BC,而 是最小樹。
例題:在同一圖執行 Prim
例題 14.2.7
(在同一圖執行 Prim)
從 A 開始,用邊堆;若取出時兩端已被選入,便捨棄該邊。A 的前沿是 AB:2, AC:3。選 AB 並加入 B;新候選包括 BC:1, BD:3,故選 BC 並加入 C。C 加入跨割候選 CD:1, CE:5(AC 此時兩端都已選,是過時項)。選 CD 並加入 D,D 又提供 DE:2。選 DE 並加入 E。所選邊是 AB:2, BC:1, CD:1, DE:2,總權重 。
這棵樹不同於 Dijkstra 樹:它用 BC 而非 AC。由 A 到 C 的樹內路徑長度為 3,與直邊相同;到 E 長度為 6。故本例的最小生成樹碰巧也達到該來源的最短距離。Dijkstra 選出的樹權重是 8,而 Prim 的樹是 6;即使某個最小生成樹碰巧也提供最短路徑,兩者目標仍不同。一般而言最小生成樹未必是最短路徑樹,反之亦然。
常見錯誤
(最短路徑樹不是最小生成樹)
上面的 Dijkstra 樹有邊 AB、AC、CD、DE,權重為 8,而最小生成樹的權重是 6。由 A 出發的最短距離和最小總權重是不同的目標,一棵樹滿足其中一個,並不表示它也滿足另一個。
追蹤在五個頂點全部入樹後結束,不需等堆清空。若圖不連通,從 A 開始的 Prim 只到達 A 的連通分量;要得到最小生成森林,須對每個餘下分量另行開始,或指定另一程序。
例題 14.2.8
(不可達的頂點與孤立頂點)
取頂點 A、B、C、D,邊為 AB:4, BC:1;D 沒有邊。由 A 出發的 Dijkstra 依次定案 A:0、B:4、C:5,永遠發現不到 D,它的標籤保持無窮大:D 不可達。由 A 出發的 Prim 接受 AB,再接受 BC,總權重為 5,此時堆已清空而 D 仍在樹外。改由 D 重新開始,得到一棵沒有邊的樹,所以最小生成森林有兩棵樹,權重為 5。
成本及檢查
鄰接表配惰性堆時,每次嚴格改善推入一項;來源頂點定案時掃描其每個有向鄰接項一次。普通二叉堆下,包含初始化的一個保守上界為時間 、空間 。若使用配有適當頂點位置映射的 decrease-key 堆,可得到熟悉的 界。這些界按所述表示法計算比較和堆操作;稠密矩陣表示有不同的掃描成本。
相信追蹤前,核實每條父邊存在、每個 Dijkstra 標籤在定案時等於父標籤加邊權,且每條報稱可達的路徑由來源開始。對 Prim,檢查每條接受邊跨越當前割、在所有跨割邊中權重最小(允許平局),並恰引入一個新頂點;有 條邊的連通結果是樹。操作計數或小例子都不能證明無條件的平均情況界。優先隊列是機制,而不變量決定它容許定案甚麼。
為何惰性堆仍取出當前最小值
命題 14.2.9
(惰性堆取出的是當前最小值)
在惰性實作中,丟棄過時項之後,第一個被接受的數對是 ,其中 是未定案頂點,其有限的當前標籤在未定案頂點中最小。
證明
(堆的一條表示不變量)
惰性實作保持具體表示不變量:每個具有有限 dist[v] 且未定案的頂點,堆內至少有一項 (dist[v],v)。初始來源項建立此性質;每次嚴格鬆弛改變標籤時都推入新項,因此保持此性質。舊項可留在堆內,但標籤不會增加。彈出時只有當鍵值仍等於當前標籤且頂點未定案,才接受該項。若有更小有限標籤的未定案頂點,其當前數對必在堆中,便不可能先取出較大的鍵。故丟棄過時項後,接受項的標籤是當前最小值。堆不變量本身只保證最小的已儲存數對;當前項和過時項規則把這事實連接到抽象 Dijkstra 不變量。
命題 14.2.10
(惰性 Dijkstra 的成本)
使用鄰接表及二叉堆時,惰性實作至多推入 個數對,時間為 ,空間為 。
證明
(計算推入與彈出的次數)
使用鄰接表,每個定案頂點的表只掃描一次。每次成功嚴格鬆弛至多產生一次新入堆;無向圖掃描的有向鄰接項至多 ,故推入至多 項,每項至多彈出一次。二叉堆包含初始化的時間為 ,包含鄰接表的空間為 。這是所述惰性表示法的最壞計數,不是期望雜湊界。簡單圖滿足 ,故 ;替換對數須使用此關係,不能對任意平行邊作未聲明假設。decrease-key 堆儲存的狀態及操作次數不同。
森林與負邊權的角色
若 Prim 的邊堆清空時仍有頂點不在 ,便沒有邊把 連至餘下頂點,表示該連通分量已完成。選另一個未訪問頂點,以空前沿重新開始;重複後每個分量各有一棵最小生成樹,孤立頂點則是沒有邊的樹。其聯集是最小生成森林:生成森林不能使用不同連通分量之間的邊,而若某個分量可換成更輕的樹,總權重便會下降。
負邊權不會破壞 Prim 的割論證;它比較跨割邊權並交換邊,兩步都不假設非負。例如兩個頂點只由權重 的邊連接,其唯一生成樹就是該邊。這與最短路徑不同:若把無向邊解作兩條有向弧,沿負邊來回會形成負權閉遊走,最短遊走問題可能沒有有限最小值。不可把 Dijkstra 的非負條件機械地套給最小生成樹,也不可把割證明套到最短路徑。
練習與詳解
快速檢查
(以「遇到相等距離便替換父節點」的規則重演惰性堆的追蹤。哪個父節點會改變?所得樹的權重是多少?)
留意 B 定案的一刻。
解答 · 答案
只有 C 的父節點改變。B 定案時,路徑 A、B、C 的長度為 3,與當前標籤相等,所以在新規則下 C 的父節點變成 B。所有距離都沒有改變。樹的邊是 AB、BC、CD、DE,總權重為 ,與 Prim 得到的是同一棵樹。
快速檢查
(在同一圖上由 C 開始執行 Prim,平局時按新頂點的字母次序決定。依次接受哪些邊?總權重是多少?)
留意哪些前沿邊會變成過時項。
解答 · 答案
由 出發,最輕的跨割邊是 CB:1 與 CD:1,平局時取 B。接著接受 CD:1。然後 BA:2 與 DE:2 同為權重 2;因為 A 排在 E 之前,先接受 BA,再接受 DE。接受次序是 CB、CD、BA、DE,總權重為 。次序與由 A 開始的執行不同,但總權重與起點無關。
快速檢查
(在第一個追蹤中,共推入多少個數對?彈出的數對中有多少個因過時而被丟棄?把推入次數與界 比較。)
按次序列出所有推入的數對。
解答 · 答案
推入的數對依次是 、、、、、、,共七個。七個都被彈出,其中恰有兩個因過時而丟棄: 與 。圖有 條邊,界為 ,實際次數符合此界。