1 概述

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

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

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

圖1: 圖例

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

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

• 性質(zhì)1: 如果從s無法到達(dá)結(jié)點(diǎn)v乓诽，則定義s到v的路徑為∞
• 性質(zhì)2: 如果圖G中的邊的權(quán)值均為確定的正整數(shù)，如果v從s可達(dá)咒程，則其對短路徑是確定的正整數(shù)
• 性質(zhì)3: 如果圖G中存在權(quán)值和為負(fù)的環(huán)路鸠天，則s到這個環(huán)路上的所有結(jié)點(diǎn)的最短路徑不存在（或者為-∞）
• 性質(zhì)4: 兩個結(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中的例子相對簡單剥纷，??(s, a) = 3，為了求??(s, b) 呢铆，因?yàn)閟到a的路徑為<s, a, b>, 所以??(s, b)=3+(-4) = -1晦鞋，依次類推。如果從s到a存在多條路徑棺克，則多條路徑中權(quán)值最小的路徑為最短路徑（顯然悠垛，可以用動態(tài)規(guī)劃求解）。現(xiàn)在的問題是：1）如何比較規(guī)整地求出所有的最短路徑的權(quán)值娜谊；2）如何保存最短路徑确买。

對于問題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)撑帖，然后按照這個公式求）。

對于問題2）澳眷，為了保存所有源結(jié)點(diǎn)為s的最短路徑胡嘿，假設(shè)其中一條路徑為< v₀, v₁, v₂, ..., v_k >，其中v₀=s钳踊，則我們需要保存最短路徑中各結(jié)點(diǎn)間的偏序關(guān)系衷敌，在此可以構(gòu)造一個前驅(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ù)兵钮，對于每個結(jié)點(diǎn)v，假設(shè)從s到v的最短距離為v.d舌界，初始時掘譬，不知道v.d的值為多少，不妨將其賦值為∞呻拌，初始化算法INITIALIZE-SINGLE-SOURCE如圖2所示（摘自算法導(dǎo)論）：

圖2: 初始化算法

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

圖3：松弛算法

3 最短路徑算法

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

3.1 Bellman-Ford算法

Bellman-Ford算法是一種最直接最笨的算法缭嫡，下面先給出算法，再對算法進(jìn)行分析說明（分析的時候有些繞抬闷，請童鞋們多思考）

圖4: Bellman-Ford算法

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

圖5: Bellman-Ford算法圖示

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

分析：設(shè)源結(jié)點(diǎn)s出發(fā)的最長的最短路徑為< v₀, v₁, v₂, ..., v_k >皇耗，v₀為s南窗，則k ≤ |G.V|-1，要得到這條路徑，考慮遍歷的最壞情況万伤，即第一遍遍歷是只能確定離s有1跳距離的??(s, v₁)窒悔，其它的??值為∞，第二遍遍歷只能確定離s有2跳距離的??(s, v₂)敌买，依次類推简珠，即在最壞情況下，循環(huán)|G.V|-1次必然能求出所有從源結(jié)點(diǎn)s出發(fā)的最短路徑虹钮。思考：再進(jìn)一步北救，如果遍歷的過程中，不是最壞情況芜抒，而是在一次循環(huán)中，遍歷邊的順序是：先訪問距s有1跳距離的邊(結(jié)點(diǎn))托启，然后再遍歷距s有2跳距離的邊(結(jié)點(diǎn))宅倒，依次類推，又會是什么情況呢屯耸？需要循環(huán)多少次拐迁？

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

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

顯然讯壶，在上面的分析中，如果遍歷邊的順序合適（即按照拓?fù)渑判蜻叺捻樞騺恚┩宓粒恍枰淮窝h(huán)即可伏蚊，這樣就可降低算法的復(fù)雜度降為O(V+E)，其算法為：

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

其分析與前面的分析類似格粪，童鞋們可以自己分析

3.2 Dijkstra算法

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

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

算法示意如下圖7所示：

圖7: Dijkstra算法

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

圖8: Dijkstra算法過程示例

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

4 總結(jié)

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