陳道蓄

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

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

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

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

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

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

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

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

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

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

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

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

● 帶權(quán)圖的最短路算法

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

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

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

1. S[B]=min{S[C]+5，S[F]+3，S[G]+2}，注意這個(gè)式子的形成規(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]的計(jì)算需要用到子問題S[v]的結(jié)果，就說前者“依賴”后者。（這個(gè)依賴關(guān)系本質(zhì)上與本專欄前面討論的調(diào)度問題中涉及的一樣，不是嗎？）這個(gè)方法稱為“動(dòng)態(tài)規(guī)劃”。動(dòng)態(tài)規(guī)劃需要計(jì)算所有的子問題，似乎會(huì)導(dǎo)致指數(shù)級的復(fù)雜度。但是如果能夠仔細(xì)地對所有子問題排序，保證被依賴的一定會(huì)先計(jì)算，并且能設(shè)計(jì)一種可以快捷地存取子問題解的方法，那么就可能設(shè)計(jì)出非常有效的算法。因此，動(dòng)態(tài)規(guī)劃是一種很重要的算法設(shè)計(jì)方法。在本專欄2020第9期的《投資組合問題》一文中用的也是動(dòng)態(tài)規(guī)劃方法（見參考文獻(xiàn)[2]）。

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

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

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

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

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

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

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

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

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

◇ enqueue（PQ，v，key）：節(jié)點(diǎn)v進(jìn)隊(duì)列PQ，其鍵值置為key

◇ dequeue（PQ）： 從隊(duì)列PQ中出一個(gè)元素，一定是隊(duì)列元素中key最小的（之一）

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

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

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

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

● 負(fù)權(quán)值的影響

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

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