1 概述

最短路徑是圖中的常見(jiàn)問(wèn)題，最典型的應(yīng)用是：當(dāng)我們用百度地圖或高德地圖引導(dǎo)我們?nèi)ツ硞€(gè)地方時(shí)，它通常會(huì)給出一個(gè)相對(duì)最短的路徑，當(dāng)然，它也有可能給出一個(gè)避開(kāi)擁堵的時(shí)間最短但路徑長(zhǎng)度不一定最短的路徑（這個(gè)也可以看成是一個(gè)路徑間權(quán)值可以變化的情況，更復(fù)雜了）。本文闡述圖中從一個(gè)給定的源結(jié)點(diǎn)s到所有其它結(jié)點(diǎn)最短的路徑。

2 相關(guān)定義和基本思路

假設(shè)圖G=(V, E)，其中V為圖中的結(jié)點(diǎn)，E為圖中所有的邊，在此，假設(shè)圖G是有向圖，對(duì)于G中的邊E，存在權(quán)重函數(shù)w: E->R，圖中的權(quán)重通常表示一個(gè)結(jié)點(diǎn)到一個(gè)結(jié)點(diǎn)之間的代價(jià)，如路徑長(zhǎng)度、耗費(fèi)時(shí)間等，在具體的場(chǎng)景中有具體的意義，本文中暫且認(rèn)為w是固定不變的（方便處理）,用??(s, v)表示結(jié)點(diǎn)s到結(jié)點(diǎn)v的最短路徑。先看圖1:

圖1: 圖例

如果要求結(jié)點(diǎn)s到所有其它結(jié)點(diǎn)的路徑，該如何處理？

首先，有幾個(gè)要點(diǎn)必須明白：

• 性質(zhì)1: 如果從s無(wú)法到達(dá)結(jié)點(diǎn)v，則定義s到v的路徑為∞
• 性質(zhì)2: 如果圖G中的邊的權(quán)值均為確定的正整數(shù)，如果v從s可達(dá)，則其對(duì)短路徑是確定的正整數(shù)
• 性質(zhì)3: 如果圖G中存在權(quán)值和為負(fù)的環(huán)路，則s到這個(gè)環(huán)路上的所有結(jié)點(diǎn)的最短路徑不存在（或者為-∞）
• 性質(zhì)4: 兩個(gè)結(jié)點(diǎn)之間的存在最短路徑< v₀, v₁, v₂, ..., v_k >，則< v₁, v₂, ..., v_k-1 >是v₁到v_k-1的最短路徑（注：直觀上很好理解，用反證法分析證明）
• 性質(zhì)5: 最短路徑中必然不存在環(huán)路（如果所有邊的權(quán)值為正整數(shù)，肯定不可能；如果存在為負(fù)值的環(huán)路，則必然不存在s到環(huán)路中結(jié)點(diǎn)的最短路徑）

圖1中的例子相對(duì)簡(jiǎn)單，??(s, a) = 3，為了求??(s, b) ，因?yàn)閟到a的路徑為<s, a, b>, 所以??(s, b)=3+(-4) = -1，依次類(lèi)推。如果從s到a存在多條路徑，則多條路徑中權(quán)值最小的路徑為最短路徑（顯然，可以用動(dòng)態(tài)規(guī)劃求解）?，F(xiàn)在的問(wèn)題是：1）如何比較規(guī)整地求出所有的最短路徑的權(quán)值；2）如何保存最短路徑。

對(duì)于問(wèn)題1），根據(jù)性質(zhì)4，要求??(s, v) ，可以先求出??(s, u)，再求w(u, v)，其中(u, v)∈E, 則必然有??(s, v) ≤ ??(s, u) + w(u, v)（分析：可以求出v的所有前驅(qū)結(jié)點(diǎn)，然后按照這個(gè)公式求）。

對(duì)于問(wèn)題2），為了保存所有源結(jié)點(diǎn)為s的最短路徑，假設(shè)其中一條路徑為< v₀, v₁, v₂, ..., v_k >，其中v₀=s，則我們需要保存最短路徑中各結(jié)點(diǎn)間的偏序關(guān)系，在此可以構(gòu)造一個(gè)前驅(qū)子圖G_??=(V_??, E_??)，其中：

• V_?? = {v ∈ V: v.?? ≠NIL} ?{s}
• E_?? = {(v.??, v) ∈E: v∈V_?? - {s}},其中v.??表示最短路徑中v的前驅(qū)（最短路徑中，除了s.?? = NIL之外，其它結(jié)點(diǎn)的前驅(qū)均不為NIL）

顯然，G_??是一顆樹(shù)或森林。如何生成這棵最短路徑的樹(shù)呢？這里需要用到松弛技術(shù)，對(duì)于每個(gè)結(jié)點(diǎn)v，假設(shè)從s到v的最短距離為v.d，初始時(shí)，不知道v.d的值為多少，不妨將其賦值為∞，初始化算法INITIALIZE-SINGLE-SOURCE如圖2所示（摘自算法導(dǎo)論）：

圖2: 初始化算法

所謂松弛技術(shù)就是通過(guò)遍歷圖中的邊，最終將v.d收斂到s到v的最短路徑，假設(shè)存在s到v的路徑s->...->u->v,如果有v.d ≥ u.d + w(u, v)，則v.d更新為u.d + w(u, v)，其對(duì)應(yīng)的松弛算法如圖3所示（摘自算法導(dǎo)論）為：

圖3：松弛算法

3 最短路徑算法

有了上面的定義和基礎(chǔ)，本節(jié)分別介紹Bellman-Ford算法和Dijkstra算法。

3.1 Bellman-Ford算法

Bellman-Ford算法是一種最直接最笨的算法，下面先給出算法，再對(duì)算法進(jìn)行分析說(shuō)明（分析的時(shí)候有些繞，請(qǐng)童鞋們多思考）

圖4: Bellman-Ford算法

圖4算法中，當(dāng)圖中存在權(quán)值為負(fù)值的環(huán)路時(shí)，返回false，否則返回true。算法看上去很簡(jiǎn)單，但是如何確定它是正確的呢？下面先把《算法導(dǎo)論》中的實(shí)例列出來(lái)，然后再對(duì)算法進(jìn)行分析。

圖5: Bellman-Ford算法圖示

接下來(lái)分析圖4中的Bellman-Ford算法的正確性。第3～4行循環(huán)|G.V|-1次，每次循環(huán)中都遍歷一次所有的邊，并且執(zhí)行松弛操作（第4行），這樣即可保證最終可得所有到源結(jié)點(diǎn)的最短路徑。為什么？

分析：設(shè)源結(jié)點(diǎn)s出發(fā)的最長(zhǎng)的最短路徑為< v₀, v₁, v₂, ..., v_k >，v₀為s，則k ≤ |G.V|-1，要得到這條路徑，考慮遍歷的最壞情況，即第一遍遍歷是只能確定離s有1跳距離的??(s, v₁)，其它的??值為∞，第二遍遍歷只能確定離s有2跳距離的??(s, v₂)，依次類(lèi)推，即在最壞情況下，循環(huán)|G.V|-1次必然能求出所有從源結(jié)點(diǎn)s出發(fā)的最短路徑。思考：再進(jìn)一步，如果遍歷的過(guò)程中，不是最壞情況，而是在一次循環(huán)中，遍歷邊的順序是：先訪問(wèn)距s有1跳距離的邊(結(jié)點(diǎn))，然后再遍歷距s有2跳距離的邊(結(jié)點(diǎn))，依次類(lèi)推，又會(huì)是什么情況呢？需要循環(huán)多少次？

在分析出2～4行必然會(huì)得到最終的最短路徑之后，如果再次遍歷一遍所有的邊，如果存在v.d > u.d + w(u, v)的情況，則說(shuō)明必然存在權(quán)值為負(fù)值的環(huán)路。

因此，Bellman-Ford算法是正確的，其復(fù)雜度也很好分析，2～4行的復(fù)雜度決定了整個(gè)算法的復(fù)雜度，為O(VE).

顯然，在上面的分析中，如果遍歷邊的順序合適（即按照拓?fù)渑判蜻叺捻樞騺?lái)），只需要一次循環(huán)即可，這樣就可降低算法的復(fù)雜度降為O(V+E)，其算法為：

圖6: 拓?fù)渑判蚝蟮淖疃搪窂剿惴?/div>

其分析與前面的分析類(lèi)似，童鞋們可以自己分析

3.2 Dijkstra算法

3.1中的Bellman-Ford算法可以看作是一種暴力算法，有沒(méi)有更好的算法呢。按照性質(zhì)4，如果存在最短路徑< v₀, v₁, v₂, ..., v_k >，則< v₀, v₁, v₂ >必然是v₀到v₂的最短路徑，能否從v₂開(kāi)始找到這條最短路徑呢？Dijkstra算法正是基于這種思想，其基本邏輯為：

假設(shè)有一個(gè)結(jié)點(diǎn)集合S，從源結(jié)點(diǎn)s到集合S中的所有的最短路徑都已經(jīng)被找到，然后從V-S中選擇最短的路徑（這里是估計(jì)的??）最小的u，將u加入到集合S，然后對(duì)從u出發(fā)的所有邊進(jìn)行松弛，直至所有的結(jié)點(diǎn)加入大S中。

算法示意如下圖7所示：

圖7: Dijkstra算法

圖7中的算法使用的是貪心算法，即每次加入結(jié)點(diǎn)u時(shí)，必然有u.d = ??(s, u) （注：這是一個(gè)直觀可以理解的結(jié)論，同樣用反證法進(jìn)行分析，具體分析時(shí)關(guān)注集合和路徑），下圖用一個(gè)示例說(shuō)明：

圖8: Dijkstra算法過(guò)程示例

分析：圖7中的算法中，每條邊僅被遍歷一次，遍歷時(shí)間為O(E), 第4的while循環(huán)會(huì)執(zhí)行|V|次，第5行獲取最小值操作時(shí)間復(fù)雜度為O(V)，因此，整個(gè)算法的時(shí)間復(fù)雜度為O(V² + E)。（當(dāng)然，根據(jù)圖是否稀疏，可以對(duì)其中的每個(gè)步驟進(jìn)行優(yōu)化，優(yōu)化后的時(shí)間復(fù)雜度取決于第5行所采用的結(jié)構(gòu)）

4 總結(jié)

本文對(duì)從單源結(jié)點(diǎn)s出發(fā)的最短路徑算法進(jìn)行了闡述，分別是Bellman-Ford算法和Dijkstra算法，并對(duì)兩個(gè)算法進(jìn)行了初步的分析，在具體使用時(shí)，后者經(jīng)常使用。圖中的算法描述本身都較為簡(jiǎn)單，但是弄清其原理并對(duì)其進(jìn)行分析才是關(guān)鍵。