最短路徑問題

陳道蓄

在道路網絡中確定起點到終點的最短路徑，可以抽象為一個有向圖模型。圖中每個節(jié)點表示一個“路口”，對任意節(jié)點u，v，存在uv-邊當且僅當從u到v有“路段”直接相連（當中沒有其他路口）。也可以建立無向圖模型，則任一條邊對應于雙向可通行的路段。其實這樣的模型并不限于道路交通問題，從本專欄前面的文章中讀者已經看到許多與交通運輸無關的問題都可以抽象為圖模型，“最短路徑”在不同應用中可能背景意義不同，但確定最短路是大量基于圖模型的應用問題求解中的一個基本環(huán)節(jié)。

● 用廣度優(yōu)先搜索（BFS）算法求解

先來考慮有向圖模型上一種最簡單的情況：假設每個路段長度均為1，那么，從u到v最短路的長度即為所有uv-路中包含的邊數的最小值，也稱為從u到v的距離。

設想房間的角上有個水龍頭，其所在位置是房間地面最高點。地面高度向房內其他地方極其平緩地均勻下降，將龍頭開到適當大小，水會在地面以扇形緩緩漫開。如果像動畫片一樣間隔固定時間段記錄漫水區(qū)域的邊界，看到的將是一道道大致平行的弧形曲線，它們反映了邊界上的點與水龍頭位置的大致距離。

在圖中遍歷所有節(jié)點常用算法包括“深度優(yōu)先（DFS）”與“廣度優(yōu)先（BFS）”。本專欄在前面討論走迷宮和調度問題時，都采用了深度優(yōu)先算法。從上面的比喻很容易想到：考慮點與點的距離時該采用廣度優(yōu)先算法。事實上，在本專欄在前面討論圖的連通性時，簡單地用到了廣度優(yōu)先（盡管我們沒有提到這個名詞）。圖1給出一個簡單的例子，指定a為起點，則廣度優(yōu)先搜索生成的BFS樹可能如圖1中右圖所示。

右邊結果圖中每個節(jié)點名稱旁標的數字表示從起點a到該點最短路的長度。在廣度優(yōu)先搜索過程中，距離a較遠的節(jié)點被發(fā)現的時間一定晚于較近的節(jié)點。

這個例子顯示了廣度優(yōu)先搜索過程與最短路徑的關聯。由此在每條邊長度均為1的假設下，我們可以用廣度優(yōu)先算法解最短路問題。

為了體現前面的比喻中漫水區(qū)前緣均勻推進，算法用隊列Q放置當前已經“看見”并等待處理的頂點。隊列“先進先出”的特性恰好符合均勻推進的需要。每個節(jié)點有兩個參數：d表示從起點到該點的距離，初始值為∞;p表示在生成的BFS樹中該點的“父節(jié)點”，初始值為nil。算法過程如下頁圖2所示。

廣度優(yōu)先搜索算法對圖中每個節(jié)點只“發(fā)現”一次，在搜索所有節(jié)點的鄰接表過程中每條邊只處理一次，因此算法的時間復雜度為O（m+n）。讀者不妨用前面的例子模擬一下隊列操作的全過程，這樣對廣度優(yōu)先算法會有更清楚的理解，并能理解為什么算法結果是正確的。嚴格的正確性證明可以基于隊列操作用數學歸納法，有興趣的讀者可以參閱文獻[1]。

在實際應用中要求每條邊長度為1是不合理的。根據應用的含義，我們給每條邊指定一個確定的數值，這稱為“權”，相應的圖稱為“（帶）權圖”。顯然圖2所示的BFS算法不能用于帶權圖。解題時可以考慮一種重要的思路——問題規(guī)約。我們會想當前的問題是否可以改造成我們已經解決的某個問題，利用那個問題的解得到當前問題的解。那么我們是否能將帶權圖規(guī)約為BFS可以處理的圖呢？如果權值均為正整數，這非常簡單。對應輸入的任意圖G（每條邊有正權值），我們按照如下方式構造圖G：G的節(jié)點集與包含G中所有節(jié)點;對應G中每條邊e（假設權值是k），在G中用一條長度為k的有向通路替換，通路的端點即G中邊e的端點，方向保持一致。通路中的k-1個中間節(jié)點是G中沒有的。G中的邊沒有權值。讀者很容易證明，基于BFS算法對G的計算結果可以得到原問題（對帶權圖G）的解。

為什么這個方法不適用？如果我們問：BFS算法的復雜度是線性的，現在還是嗎？讀者是否能回答？

順便提一個問題：深度優(yōu)先算法中先被發(fā)現的節(jié)點一定比后發(fā)現的“后裔節(jié)點”更晚關閉（回溯），這就需要采用“后進先出”的棧結構;但大家在本專欄前面討論走迷宮或調度問題的DFS過程中并沒有看到明確地使用棧結構，這是為什么呢？

● 帶權圖的最短路算法

可以將帶權圖理解為輸入除了上述的G和s外還包括一個函數w，其定義域為圖中的邊集，值域通常是數集。簡單說每條邊有個確定的數值，其應用含義可以是相應路段的長度、運輸成本、通過時間等（在與道路交通無關的應用中也可以是其他任意合理解釋）。一條通路的權值定義為它包含的所有邊的權值之和，因此，最短路問題就是找出總權值最小的路徑。注意，如果圖中s可以通達某個總權值為負值的回路，“最短”就無意義了。本文假設所有邊的權值均非負。圖3是一個帶權有向圖的例子。

假設我們需要計算圖中從節(jié)點A到B的最短路，最“樸素”的貪心策略不能保證找到正確的解。假如從A開始我們始終選擇“當前”頂點所關聯的權最小的邊前行，結果是A-D-E-F-B，路徑長度為9。但是路徑A-D-G-B長度為7（這確實是最優(yōu)解）。

有一種方法可以保證找到最優(yōu)解。用S[v]表示從A到v最短路的長度，從終點“反推”，可得：

1. S[B]=min{S[C]+5，S[F]+3，S[G]+2}，注意這個式子的形成規(guī)則

2.? S[G]=min{S[D]+2，S[E]+3，S[F]+4}

3.? S[F]=min{S[C]+2，S[D]+2，S[E]+3}

4.? S[C]=min{4，S[D]+5}= 4

5.? S[E]=min{5，S[D]+1}

6.? S[D]=3

從下往上逐次代入，很容易得到：S[B]=7。這就是最優(yōu)解。我們可以將S[v]看作待解問題的子問題。如果子問題S[u]的計算需要用到子問題S[v]的結果，就說前者“依賴”后者。（這個依賴關系本質上與本專欄前面討論的調度問題中涉及的一樣，不是嗎？）這個方法稱為“動態(tài)規(guī)劃”。動態(tài)規(guī)劃需要計算所有的子問題，似乎會導致指數級的復雜度。但是如果能夠仔細地對所有子問題排序，保證被依賴的一定會先計算，并且能設計一種可以快捷地存取子問題解的方法，那么就可能設計出非常有效的算法。因此，動態(tài)規(guī)劃是一種很重要的算法設計方法。在本專欄2020第9期的《投資組合問題》一文中用的也是動態(tài)規(guī)劃方法（見參考文獻[2]）。

現在我們來介紹非常著名的Dijkstra算法。Dijkstra算法用非常簡單的貪心策略的“形”，包裹了動態(tài)規(guī)劃算法保證正確的“魂”，卻又針對問題的特征，避免了煩瑣的子問題定義與結果存取，采用逐個為圖中節(jié)點加標號（在算法執(zhí)行過程中，標號的值即從起點到該節(jié)點當前已發(fā)現的最短路徑長度值，尚未“被發(fā)現”的節(jié)點標號值為“無窮大”）的方式計算從起點s到圖中所有其他節(jié)點的最短路長度（也稱距離）。因為算法計算的是從特定起點到其他所有點的最短路，所以通常稱為“單源最短路算法”。

為了使讀者更容易理解Dijkstra算法，我們把前面關于水龍頭的比喻放在圖模型的背景下重新表述一下：往一張宣紙上緩緩地潑墨，首先將起點s覆蓋，然后在算法控制下逐步擴大“墨點”覆蓋范圍。在任一特定時刻，墨跡覆蓋區(qū)域有一個邊界。如果采用上面討論動態(tài)規(guī)劃時的說法，界內的點u相應的子問題S[u]已解;從加標號的角度說，界內節(jié)點的標號已經固定，不會再被改變，這就是從s到該點最短路的長度值。另一方面，與邊界內任一節(jié)點相鄰的外部點是“當前可見”的。

每次擴大“墨點”總是選擇尚未被覆蓋但“可見”的節(jié)點中標號最小的。開始時s標號為0，其他節(jié)點標號均為∞。每當一個節(jié)點v被覆蓋（從s開始），與其相鄰的點u的標號將更新為min{u原標號值，v標號值+w（vu）}，其中w（vu）是vu-邊的權值。任何可見但尚未被覆蓋節(jié)點的標號在每次循環(huán)中均可能被改變，這取決于是否發(fā)現了從s到該點的更短的路徑（可以比較一下動態(tài)規(guī)劃過程）。當全部節(jié)點均被覆蓋時算法終止。

若圖中節(jié)點數為n，則上述“墨點擴散”通過n-1次循環(huán)完成，圖4針對前面的例子，給出前4次循環(huán)形成的“墨跡”邊界示意。每次循環(huán)確定一個節(jié)點的“固定”標號，操作序列為：A（0），D（3），C（4），E（4）。已覆蓋的點在圖中用黑體字標注標號，注意，E的標號在D被覆蓋時由5更新為4。本文中算法在標號值相等時按照節(jié)點名字母順序執(zhí)行。目前，B，F，G也均“可見”，因此均具有有限標號值。注意，隨著F與G先后被覆蓋，B的標號值還將更新兩次，最終達到7。

從上面的描述中讀者應該很容易理解Dijkstra算法的基本邏輯：通過一個循環(huán)過程，以盡量減小已有標號的方式將所有節(jié)點的標號固定下來，最終達到從s到各節(jié)點的最短路長度值。對初學者而言，最難理解的地方可能在于：每次擴大“墨跡”新覆蓋的節(jié)點究竟是如何確定的。當然在每次循環(huán)中，在所有可見的節(jié)點中找出最小元素，這顯得有些笨拙，因為可見的節(jié)點數可能接近n。

在描述Dijkstra算法之前，我們先來介紹一種對算法設計非常有價值的思維方法——數據抽象。為了解決單源最短路問題，我們希望每次循環(huán)中從“可見”的節(jié)點中選擇標號值最小的。假設這些節(jié)點以某種形式存放著，有一個節(jié)點選取操作，總是返回其中標號值最小的元素，那么算法層面的考慮就很簡單了。至于怎么能實現這一點，到編程時再考慮。這就稱為“數據抽象”，顯然它可以使我們在設計算法時避免編程細節(jié)的糾纏，聚焦于解題邏輯。

數據抽象在編程實踐中常以抽象數據類型的形式體現。對這個例子而言，人們常用的是“最小優(yōu)先隊列”（priorityQ），它按照key的值定義“優(yōu)先級”，出隊列總是“優(yōu)先級”最高的元素。這里key即標號值，小的優(yōu)先。注意，一般的隊列可以認為是“優(yōu)先隊列”的特例，key為進隊列時間，時間值小的優(yōu)先。key的值可以設置，也可以修改。

我們建立一個最小優(yōu)先隊列類型的對象PQ，其元素為圖G中所有“可見但標號尚未固定”的節(jié)點（也就是“緊鄰墨跡區(qū)”的外部節(jié)點）。我們需要該結構提供如下操作：

◇ create（）： 創(chuàng)建最小優(yōu)先隊列類型的對象

◇ enqueue（PQ，v，key）：節(jié)點v進隊列PQ，其鍵值置為key

◇ dequeue（PQ）： 從隊列PQ中出一個元素，一定是隊列元素中key最小的（之一）

◇ decreaseKey（PQ，v，key）：將已經在隊列PQ中的對象v的鍵值降為key，在算法過程中，當從s到已被發(fā)現但尚未完成的v找到一條更短的通路時，需要這個操作

基于優(yōu)先隊列的Dijkstra算法過程見圖5。過程中假設抽象數據類型priorityQ已定義。本文中不討論其實現。用二進堆（binary heap）實現的細節(jié)可參考文獻[1]。Python語言中提供的class為抽象數據類型實現提供了方便。有興趣的讀者不妨試一試，并在此基礎上編寫完整的解單源最短路問題的程序。

下頁圖6顯示上述過程前6次循環(huán)執(zhí)行效果。最后一次（第7次）只會將B點置為黑色。

Dijkstra算法的正確性基于論斷“第k+1次循環(huán)即將開始時，有k個節(jié)點狀態(tài)為“black”，此后這些節(jié)點的標號不會再更新，且其值為從s到這些點各自的最短路長度”。這個論斷可以通過對k用數學歸納法證明。初略地看，算法執(zhí)行n次循環(huán)，每次循環(huán)最多從n個節(jié)點中選標號的最小值。在加標號過程中每條邊也只需檢查一次。這是一個O（n2+m）算法，m表示圖中的邊數。讀者已經看到利用優(yōu)先隊列，不需要每次遍歷查找最小元素，但每次進出隊列操作后維護優(yōu)先隊列的特性（即出隊列的一定是優(yōu)先級最高的元素）需要代價。精心設計的實現方法可以使Dijkstra算法的時間復雜度達到O（nlogn+m），對應用中比較普遍的非稠密圖（邊數只是節(jié)點數的常數倍，而非平方數量級），這顯然好于O（n2）。

● 負權值的影響

輸入中不能含有總權值為負的回路，這很容易理解。但前面特別說明不能有負權值的邊，這要求更高，這是為什么呢？

前面介紹過“問題規(guī)約”的思路。讀者可能會想到如果輸入中包含負權值的邊，我們是否可以通過規(guī)約的方式消除負權值？原圖中所有負權值一定有絕對值最大的，如t。假如將所有邊的權值均加t，那就沒有負權值了。下頁圖7是一個帶負權值的圖的例子。