先聊一個問題導(dǎo)航App輸入起點(diǎn)和終點(diǎn)它怎么在幾秒內(nèi)算出最優(yōu)路線剝開外殼底層大多是一個經(jīng)典算法——單源最短路徑而其中應(yīng)用最廣、最適合入門的就是Dijkstra算法。Dijkstra解決的問題非常具體在一張帶權(quán)圖上給定一個源點(diǎn)求它到所有其他節(jié)點(diǎn)的最短距離。這里的權(quán)可以是時間、距離、成本條件是權(quán)重非負(fù)。只要滿足這個條件Dijkstra就是最優(yōu)先考慮的方案。這篇文章會從最短路徑問題的定義開始拆解Dijkstra的貪心原理給出樸素實現(xiàn)和堆優(yōu)化兩份可直接抄的代碼再聊聊我實際刷題和工程里踩過的那些坑。適合剛學(xué)完圖論基礎(chǔ)、想把最短路徑徹底吃透的讀者。1. 最短路徑問題與Dijkstra的定位1.1 圖上的最短路徑到底在求什么先建立基本概念。圖由節(jié)點(diǎn)和邊組成每條邊可能帶有一個權(quán)重代表從這條邊一端到另一端的代價。最短路徑問題就是在給定起點(diǎn)和終點(diǎn)之間找一條路徑使得路徑上所有邊的權(quán)重之和最小。如果圖沒有權(quán)重也就是每條邊代價都是1那最短路就等價于最少經(jīng)過幾條邊。這種情況BFS就夠了。但一旦邊有了權(quán)重比如地鐵換乘時間、公路里程、運(yùn)費(fèi)成本BFS就失效了——它只數(shù)邊數(shù)不看權(quán)重哪怕一條路只有兩段但每段都很貴BFS依然認(rèn)為它最短。Dijkstra算法處理的就是這種帶權(quán)圖的單源最短路徑。意思是每次只算一個起點(diǎn)一次性得出這個點(diǎn)到所有其他點(diǎn)的最短距離。與之相對的是Floyd這類全源算法一次算所有點(diǎn)對之間的最短路。實際場景中絕大多數(shù)是單源需求所以Dijkstra出鏡率極高。1.2 所有權(quán)重非負(fù)這個前提為什么繞不開很多初學(xué)者不理解為什么Dijkstra一定要求邊權(quán)非負(fù)負(fù)權(quán)邊到底會出什么問題我用一個極簡的反例說明。假設(shè)有一個三角形起點(diǎn)A直接到終點(diǎn)B邊權(quán)是5同時A到中間節(jié)點(diǎn)C的邊權(quán)是1C到B的邊權(quán)是-3。按真實答案A到B的最短路是A-C-B總代價1 (-3) 2比直連的5更短。然而Dijkstra的貪心策略是每次先鎖定當(dāng)前距離最小的點(diǎn)。第一輪它發(fā)現(xiàn)A到B的直連距離是5A到C是1于是它會鎖定C第二輪再鎖定B這樣算出的結(jié)果是A-C-B看起來碰巧對了。但換個結(jié)構(gòu)就不行。比如A到B是5A到C是1C到B是-10。Dijkstra第一輪會鎖定C然后更新B為1 (-10) -9看起來也還行。問題出在更復(fù)雜的圖上當(dāng)C的距離其實還能被其他負(fù)邊進(jìn)一步縮小但C已經(jīng)被鎖定后續(xù)不會再重新考慮。真正的反例A到C是1C有一條負(fù)邊連到B比如-5同時A到B直連是3。Dijkstra先鎖定C更新B為1-5-4隨后鎖定B。這看起來好像沒問題。但只要有負(fù)邊讓某個已鎖定節(jié)點(diǎn)的距離可以更小的結(jié)構(gòu)貪心的已鎖定則不再修改假設(shè)就被擊穿。本質(zhì)上Dijkstra依賴一個關(guān)鍵性質(zhì)從源點(diǎn)出發(fā)已經(jīng)確定的最短路徑不會被后續(xù)發(fā)現(xiàn)的路徑追平或追超。這個性質(zhì)在高權(quán)值下天然成立因為繞路只會增加代價。一旦出現(xiàn)負(fù)權(quán)邊繞路反而可能讓總代價變小那先鎖定近點(diǎn)、后處理遠(yuǎn)點(diǎn)的順序就完全不可靠了。所以結(jié)論很簡單圖里有負(fù)權(quán)邊就別用Dijkstra換Bellman-Ford或者SPFA。這是個模型選擇的問題不是代碼水平的問題。2. 算法原理拆解貪心、松弛、鎖定2.1 每個循環(huán)都在做哪幾件事Dijkstra的核心可以壓縮成三個動作貪心選擇、松弛更新、鎖定節(jié)點(diǎn)。每次循環(huán)先從未鎖定的節(jié)點(diǎn)中找出當(dāng)前距離源點(diǎn)最近的那個把它標(biāo)記為已確定。這個已確定的意思是這個距離已經(jīng)是最終答案后續(xù)不會再變得更小。然后拿著這個節(jié)點(diǎn)遍歷它的所有出邊嘗試用它更新鄰居的距離。更新邏輯很簡單如果源點(diǎn)經(jīng)過當(dāng)前節(jié)點(diǎn)再到鄰居的總代價比鄰居現(xiàn)有的記錄還要小就覆蓋鄰居的記錄。這個過程叫松弛。松弛這三個字理解透了整個算法也就理解了。可以用一個生活場景類比假設(shè)你在幾個倉庫之間轉(zhuǎn)運(yùn)貨物每個倉庫都有一個當(dāng)前估算成本。發(fā)現(xiàn)經(jīng)某個倉庫中轉(zhuǎn)可以更省錢就更新這個估算值。每次只挑估算成本最低的倉庫來鋪路鋪過路的倉庫就被標(biāo)記成最終成本以后不再改。松弛不是只做一次而是隨著新節(jié)點(diǎn)不斷被確定而反復(fù)進(jìn)行。每一輪松弛都可能讓某個鄰居的估算值變小。整個算法終止條件也很簡單所有能到達(dá)的節(jié)點(diǎn)都被鎖定優(yōu)先隊列被清空。2.2 一個五節(jié)點(diǎn)圖的手動推演光看概念容易飄我拿一個具體的圖走一遍全過程。這是一個無向圖5個節(jié)點(diǎn)編號0到4源點(diǎn)是0。邊的關(guān)系如下0-1: 權(quán)重40-2: 權(quán)重21-2: 權(quán)重11-3: 權(quán)重52-3: 權(quán)重82-4: 權(quán)重103-4: 權(quán)重2初始狀態(tài)dist數(shù)組為[0, ∞, ∞, ∞, ∞]0號節(jié)點(diǎn)距離是0其他都是無窮大。優(yōu)先隊列放入(0, 0)。第一輪彈出(0, 0)鎖定節(jié)點(diǎn)0。遍歷它的鄰居節(jié)點(diǎn)1被更新為0 4 4節(jié)點(diǎn)2被更新為0 2 2。dist變?yōu)閇0, 4, 2, ∞, ∞]。第二輪優(yōu)先隊列里最小的是距離2的節(jié)點(diǎn)2鎖定節(jié)點(diǎn)2。用節(jié)點(diǎn)2更新鄰居節(jié)點(diǎn)1經(jīng)過2是2 1 3比原來的4小更新為3節(jié)點(diǎn)3經(jīng)過2是2 8 10節(jié)點(diǎn)4經(jīng)過2是2 10 12。dist變?yōu)閇0, 3, 2, 10, 12]。注意這里節(jié)點(diǎn)1的距離在第1輪被設(shè)為4但在第2輪通過節(jié)點(diǎn)2中轉(zhuǎn)反而更短所以被更新成了3。這就是松弛存在的意義最初的距離估算只是臨時值隨時可能被更優(yōu)路徑替代。第三輪未鎖定節(jié)點(diǎn)中最小的是距離3的節(jié)點(diǎn)1鎖定節(jié)點(diǎn)1。用節(jié)點(diǎn)1更新鄰居節(jié)點(diǎn)3走1是3 5 8比原來的10小更新為8。dist變?yōu)閇0, 3, 2, 8, 12]。第四輪未鎖定節(jié)點(diǎn)中最小的是距離8的節(jié)點(diǎn)3鎖定節(jié)點(diǎn)3。用節(jié)點(diǎn)3更新鄰居節(jié)點(diǎn)4走3是8 2 10比原來的12小更新為10。dist變?yōu)閇0, 3, 2, 8, 10]。第五輪鎖定節(jié)點(diǎn)4距離10沒有更小的鄰居可更新。最終結(jié)果dist [0, 3, 2, 8, 10]。也就是說0到4的最短距離是10路徑是0-2-1-3-4而不是看起來更直接、但繞遠(yuǎn)的那條0-2-4總代價12。這個例子值得多看兩眼。最短路不一定是邊數(shù)最少的路徑0到4有直連邊但代價很高反而是多轉(zhuǎn)幾次的路徑總代價更小。這也是帶權(quán)圖和無權(quán)圖的本質(zhì)區(qū)別。2.3 貪心為什么有效一個簡明的正確性直覺Dijkstra是典型的貪心算法。貪心算法并不總能保證最優(yōu)解為什么Dijkstra能保證關(guān)鍵在于下一跳鎖定距離最小的點(diǎn)這個策略。直觀地理解所有邊權(quán)都是非負(fù)的那么任何一條從源點(diǎn)出發(fā)、經(jīng)過某個未鎖定節(jié)點(diǎn)再繞回來的路徑其總長度一定不會小于這個未鎖定節(jié)點(diǎn)到源點(diǎn)的當(dāng)前距離。因為繞路必然還要加上若干條非負(fù)的邊權(quán)只會讓總長度更大。所以當(dāng)從未鎖定節(jié)點(diǎn)中選出距離最小的節(jié)點(diǎn)u時可以確定如果存在一條比dist[u]更短的路到達(dá)u這條路上必然第一個遇到某個未鎖定節(jié)點(diǎn)v。那么v到源點(diǎn)的距離應(yīng)該比dist[u]更小否則經(jīng)過v的路徑不可能比dist[u]短——這與u是所有未鎖定節(jié)點(diǎn)中距離最小的矛盾。這個矛盾說明了什么說明dist[u]已經(jīng)小到不可能再有更優(yōu)路徑了所以放心鎖定。非負(fù)邊權(quán)是這個論證的基石任何繞路都不會帶來負(fù)收益這保證了目前最小就是最終最小。3. 代碼實現(xiàn)先樸素再堆優(yōu)化3.1 樸素實現(xiàn)O(V2)的直白寫法樸素版本不借助優(yōu)先隊列每一輪循環(huán)手動找最小距離節(jié)點(diǎn)。邏輯最簡單適合剛學(xué)完原理、準(zhǔn)備寫第一份代碼的讀者。代碼用Python寫def dijkstra_naive(n, edges, source): # n: 節(jié)點(diǎn)數(shù)量節(jié)點(diǎn)編號為 0 ~ n-1 # edges: 邊列表每個元素是 [u, v, w] adj [[] for _ in range(n)] for u, v, w in edges: adj[u].append((v, w)) adj[v].append((u, w)) # 無向圖需雙向建邊有向圖去掉這一行 INF 10 ** 18 dist [INF] * n dist[source] 0 visited [False] * n for _ in range(n): # 1. 貪心選擇從未鎖定的節(jié)點(diǎn)里找距離最小的 u -1 best INF for i in range(n): if not visited[i] and dist[i] best: best dist[i] u i if u -1: break # 剩余節(jié)點(diǎn)均不可達(dá) # 2. 鎖定節(jié)點(diǎn) u visited[u] True # 3. 松弛用 u 更新所有鄰居 for v, w in adj[u]: nd dist[u] w if nd dist[v]: dist[v] nd return dist每輪循環(huán)通過遍歷所有節(jié)點(diǎn)來找最小值所以外層循環(huán)n次內(nèi)層找最小值又是O(n)總體復(fù)雜度O(n2)。再加上遍歷鄰居松弛的O(E)整體是O(n2 E)在稠密圖中E接近n2所以綜合說O(n2)。這個版本適合什么場景節(jié)點(diǎn)規(guī)模在幾百到一兩千級別。小圖頻繁做最短路徑查詢的時候比如地圖上的局部路徑規(guī)劃、小規(guī)模網(wǎng)絡(luò)拓?fù)浞治鰳闼貙懛ㄍ耆珘蛴么a明確、不易寫錯。3.2 堆優(yōu)化實現(xiàn)標(biāo)準(zhǔn)競賽與工程寫法當(dāng)節(jié)點(diǎn)數(shù)到達(dá)10?級別甚至10?樸素實現(xiàn)的O(n2)循環(huán)直接超時。此時需要優(yōu)先隊列來快速取出最小距離節(jié)點(diǎn)時間復(fù)雜度降到O((VE)logV)。import heapq def dijkstra_heap(n, edges, source): adj [[] for _ in range(n)] for u, v, w in edges: adj[u].append((v, w)) adj[v].append((u, w)) # 無向圖需雙向建邊 INF 10 ** 18 dist [INF] * n dist[source] 0 visited [False] * n pq [(0, source)] # 優(yōu)先隊列元素是 (當(dāng)前距離, 節(jié)點(diǎn)編號) while pq: d, u heapq.heappop(pq) if visited[u]: continue visited[u] True for v, w in adj[u]: nd d w if nd dist[v]: dist[v] nd heapq.heappush(pq, (nd, v)) return dist這段代碼是工程和競賽中最常見的版本有幾個細(xì)節(jié)值得仔細(xì)講。優(yōu)先隊列的排序依據(jù)是元組第一個元素也就是距離。Python的heapq實現(xiàn)的是最小堆每次彈出的都是當(dāng)前隊列里距離最小的節(jié)點(diǎn)。這里非常重要的一個地方為什么彈出后要判斷visited因為同一個節(jié)點(diǎn)可能被多次加入優(yōu)先隊列。比如節(jié)點(diǎn)v先通過一條代價為10的路徑被加入隊列后來又發(fā)現(xiàn)一條代價為5的路徑那么v就會入隊兩次——一次(10, v)一次(5, v)。優(yōu)先隊列按距離排序所以(5, v)會先被彈出v被鎖定dist[v]5也已經(jīng)是最終值。等到(10, v)彈出時v已經(jīng)visited直接跳過即可。判斷visited就是清理這種過期記錄。3.3 visited標(biāo)記時機(jī)一個特別容易翻車的細(xì)節(jié)我剛學(xué)Dijkstra時踩過一個大坑在把新距離push進(jìn)優(yōu)先隊列的同時就把節(jié)點(diǎn)標(biāo)記為visited。后來發(fā)現(xiàn)這個寫法在某些圖上會算錯。問題出在哪看剛才那個例子。源點(diǎn)0先通過直連邊找到節(jié)點(diǎn)1距離是4。如果在push時就標(biāo)記visited節(jié)點(diǎn)1被立即鎖定。但稍后節(jié)點(diǎn)2被處理發(fā)現(xiàn)經(jīng)過節(jié)點(diǎn)2到節(jié)點(diǎn)1只需要3本應(yīng)更新dist[1]為3但由于節(jié)點(diǎn)1已經(jīng)被標(biāo)記visited這個更新就被跳過了最終答案錯誤。正確的做法是在彈出節(jié)點(diǎn)時才標(biāo)記visited入隊時不標(biāo)記。這樣即使一個節(jié)點(diǎn)被push了多次只要最終更優(yōu)的距離尚未被處理它就還有機(jī)會被重新計算和更新。一句話記住visited的含義是此節(jié)點(diǎn)的最短距離已經(jīng)被確定并鎖定而只有彈出那一刻才是真正確定的時刻。push時標(biāo)記等于把還沒確定的臨時值當(dāng)成了最終值。4. 復(fù)雜度、正確邊界與算法選型4.1 兩個版本的復(fù)雜度差異該怎么選先整理清楚兩個版本的開銷來源。樸素版本外層n輪找最小節(jié)點(diǎn)掃一遍O(n)總復(fù)雜度O(n2)。空間上如果使用鄰接矩陣是O(n2)使用鄰接表則是O(n E)。堆優(yōu)化版本每個節(jié)點(diǎn)可能入隊多次但總體上每個節(jié)點(diǎn)的入隊次數(shù)等于它被松弛更新的次數(shù)不超過E次所以總的push數(shù)量是O(E)。每次push和pop都是O(logV)?？倧?fù)雜度O((V E)logV)。堆的額外空間是O(E)。選型邏輯我琢磨過之后總結(jié)成一個判斷表圖的特點(diǎn)推薦實現(xiàn)原因節(jié)點(diǎn)數(shù)≤103稠密圖樸素找最小值的O(n)掃描開銷可接受實現(xiàn)簡單節(jié)點(diǎn)數(shù)10?~10?稀疏圖堆優(yōu)化堆的logV開銷遠(yuǎn)小于O(n)線性掃描節(jié)點(diǎn)數(shù)10?以上只能用堆優(yōu)化樸素?zé)o法在時限內(nèi)跑完圖非常稠密且節(jié)點(diǎn)數(shù)大堆優(yōu)化仍可行但可考慮鄰接矩陣需要用鄰接矩陣存邊的權(quán)重工程實踐里還有個細(xì)節(jié)因為堆優(yōu)化需要存儲邊、堆、距離數(shù)組內(nèi)存開銷比樸素更大所以小數(shù)據(jù)量時用樸素實現(xiàn)反而更穩(wěn)尤其在一些內(nèi)存受限的嵌入式環(huán)境里。4.2 與其他最短路算法的邊界對比Dijkstra不是萬能的很多人學(xué)完它就不管其他了遇到負(fù)權(quán)圖照樣跑然后莫名其妙得出錯誤結(jié)果。我把幾個常見算法放在一起對比方便構(gòu)建全局認(rèn)知。算法是否允許負(fù)權(quán)邊適用場景時間復(fù)雜度特點(diǎn)BFS僅限邊權(quán)全部為1無權(quán)圖O(V E)實現(xiàn)最簡單Dijkstra不允許單源非負(fù)權(quán)圖O(V2)或O((VE)logV)最快且最常用Bellman-Ford允許無負(fù)環(huán)單源帶負(fù)權(quán)圖O(VE)可以檢測負(fù)環(huán)SPFA允許無負(fù)環(huán)單源帶負(fù)權(quán)圖平均O(E)最壞O(VE)競賽常用但易被卡Floyd允許無負(fù)環(huán)全源小圖O(V3)代碼簡單但只適合小圖這里我最想強(qiáng)調(diào)的是判斷一個圖能不能用Dijkstra第一件事就是檢查負(fù)權(quán)邊。怎么檢查像哪里有負(fù)權(quán)這個問題在實際場景中幾乎等于哪里有回扣、補(bǔ)貼、逆向流動這類反常規(guī)則。比如物流問題里可能出現(xiàn)空車返程成本為負(fù)的情況嗎一般情況下不會但如果你在做帶獎勵的路徑規(guī)劃就要警惕了。4.3 雙向Dijkstra讓效率再翻一倍在真實導(dǎo)航和大規(guī)模圖場景中另一個常見的加速思路是雙向Dijkstra。從起點(diǎn)和終點(diǎn)同時做Dijkstra兩個搜索前沿在中途相遇時就找到了最短路徑。這個思路聽起來簡單但實現(xiàn)時有個關(guān)鍵點(diǎn)不是兩個方向分別跑完再拼接而是交替推進(jìn)每次選擇當(dāng)前隊列中距離較小的那個方向擴(kuò)展。當(dāng)兩個前沿的節(jié)點(diǎn)訪問集合產(chǎn)生交集時就可以用交點(diǎn)的前后距離和來嘗試更新答案。如果方向選擇不當(dāng)最優(yōu)路徑可能被錯過。雙向Dijkstra的加速效果在稀疏圖上非常明顯尤其源點(diǎn)與終點(diǎn)距離較遠(yuǎn)時搜索空間從整張圖縮小為兩片前沿相交的區(qū)域。工程中的地圖路徑規(guī)劃往往用這種變種。5. 實戰(zhàn)中的常見問題與避坑實錄5.1 負(fù)權(quán)邊和負(fù)環(huán)換了算法就能解決嗎前文說過負(fù)權(quán)邊不能用Dijkstra但換Bellman-Ford后還會遇到另一個問題負(fù)環(huán)。負(fù)環(huán)是指圖中存在一個環(huán)環(huán)上所有邊權(quán)之和為負(fù)數(shù)。如果存在負(fù)環(huán)最短路就沒有意義了——每繞一圈距離就小一點(diǎn)可以無限繞下去得到任意小的距離。實際工程里怎么發(fā)現(xiàn)負(fù)環(huán)Bellman-Ford做V-1輪松弛后如果再進(jìn)行第V輪還能松弛成功就說明存在負(fù)環(huán)。實際開發(fā)中碰到這種情況往往不是算法問題而是數(shù)據(jù)建模有問題。我見過一個做運(yùn)輸優(yōu)化的團(tuán)隊把補(bǔ)貼建模成負(fù)權(quán)邊結(jié)果怎么跑都跑不出穩(wěn)定答案最后發(fā)現(xiàn)負(fù)環(huán)鏈。正確做法是把這種補(bǔ)貼放進(jìn)約束條件而不是直接寫成負(fù)邊。所以遇到負(fù)權(quán)場景先問自己這個負(fù)權(quán)重是不是合理存在如果只是數(shù)據(jù)噪聲導(dǎo)致個別負(fù)值可能修數(shù)據(jù)更現(xiàn)實如果模型本身允許負(fù)向反饋才該上Bellman-Ford。5.2 重邊、自環(huán)、雙向邊與INF取值實際建圖時重邊、自環(huán)這些臟數(shù)據(jù)經(jīng)常出現(xiàn)。我自己處理過一張上百萬邊的圖數(shù)據(jù)里相同端點(diǎn)對出現(xiàn)了三四次權(quán)值還不一樣。處理重邊的思路很簡單不需要預(yù)先合并。堆優(yōu)化Dijkstra天然處理重邊——它會先通過權(quán)值較小那條邊更新dist權(quán)值較大的邊即使later入隊也會被visited邏輯跳過。唯一需要注意的是如果使用鄰接矩陣就要在輸入時取最小值覆蓋。自環(huán)更簡單。非負(fù)權(quán)邊的自環(huán)dist[u] w dist[u]永遠(yuǎn)不會松弛成功可以忽略。就算權(quán)值為0也是白忙活邏輯上不會出錯只是多遍歷一次空操作。雙向邊要注意建圖兩側(cè)都加。這個口子漏的人特別多我用一個無向圖測試數(shù)據(jù)跑了半天結(jié)果最短距離對但路徑還原始終不對最后發(fā)現(xiàn)讀入時只建了單向邊。INF取值也值得單獨(dú)說。不要用float(inf)在需要嚴(yán)格整數(shù)比較的場景里硬扛尤其是在計算過程中做dist[u] w時如果dist[u]是float(inf)加上權(quán)重依然是infPython里沒問題但在C里用INT_MAX就可能溢出成負(fù)數(shù)。穩(wěn)妥做法是定義一個足夠大的數(shù)比如節(jié)點(diǎn)數(shù)上限乘邊權(quán)上限再加一點(diǎn)余量。我習(xí)慣用101?因為絕大多數(shù)題目的邊權(quán)和不會超過這個數(shù)量級。5.3 從求距離進(jìn)階到還原路徑大多數(shù)講解止步于求出最短距離但工程里經(jīng)常還要知道具體路徑。還原的實現(xiàn)不復(fù)雜在松弛成功時額外記錄一下節(jié)點(diǎn)v是從哪個節(jié)點(diǎn)u更新來的。用一個prev數(shù)組初始化為-1每次nd dist[v]時prev[v] u。從終點(diǎn)倒推即可得到完整路徑從終點(diǎn)出發(fā)沿著prev一路回溯到起點(diǎn)最后反轉(zhuǎn)數(shù)組。我寫個標(biāo)準(zhǔn)還原代碼def get_path(prev, source, target): path [] cur target while cur ! -1: path.append(cur) if cur source: break cur prev[cur] path.reverse() return path # 如果 path[0] ! source說明 target 不可達(dá)這個代碼有個隱含要求必須保證最短路只有一條。如果存在多條距離相同的路徑prev記錄的只是其中一條。想求字典序最小的最短路需要在松弛時增加一個比較條件距離更小或者距離相等但節(jié)點(diǎn)編號更小才更新prev。路徑還原里的另一個坑是如果節(jié)點(diǎn)不可達(dá)prev鏈在源點(diǎn)之前就斷掉上面代碼會死循環(huán)因為cur一直回退到-1還找不到source。所以退出條件要寫周全我上面的代碼用if cur source: break來保障。5.4 常用樣例自查清單我開發(fā)時習(xí)慣準(zhǔn)備一組小樣例來做回歸測試推薦你也這樣做。第一組線性圖。0-1權(quán)重11-2權(quán)重1源點(diǎn)0到2應(yīng)該是2。第二組兩個路徑對比的圖。0直連2權(quán)重100-1權(quán)重11-2權(quán)重1答案應(yīng)該是2而不是10。這個樣例專門測試松弛邏輯。第三組重邊圖。0-1權(quán)重50-1權(quán)重1答案應(yīng)該是1。第四組自環(huán)圖。0-1含0-0自環(huán)加一條權(quán)重2的邊答案2自環(huán)不干擾。第五組不可達(dá)節(jié)點(diǎn)。0連12孤立dist[2]INF不會進(jìn)入死循環(huán)。這五組樣例能在5分鐘內(nèi)覆蓋90%的基礎(chǔ)錯誤。每次寫完Dijkstra先跑一遍再過數(shù)據(jù)。6. 應(yīng)用場景與后續(xù)擴(kuò)展路線6.1 真實世界里的DijkstraDijkstra的應(yīng)用范圍遠(yuǎn)超想象。最常見的當(dāng)然是地圖導(dǎo)航。地圖軟件在預(yù)處理階段會把路網(wǎng)抽象成圖路口是節(jié)點(diǎn)路段是邊權(quán)重可以是距離、耗時或消耗。用戶請求導(dǎo)航時后排一個堆優(yōu)化的Dijkstra或者雙向變種很快就能給出路線。在計算機(jī)網(wǎng)絡(luò)領(lǐng)域鏈路狀態(tài)路由協(xié)議OSPF內(nèi)部就使用SPF算法計算最短路徑SPF本質(zhì)就是Dijkstra的工程變形。路由器維護(hù)一張全網(wǎng)拓?fù)涞逆溌窢顟B(tài)數(shù)據(jù)庫需要路由時快速計算到所有目標(biāo)的最短路徑。這里圖的規(guī)模可能達(dá)到上萬個節(jié)點(diǎn)堆優(yōu)化版本在性能和穩(wěn)定性上都經(jīng)得起考驗。游戲?qū)ぢ芬彩侵貫?zāi)區(qū)。很多游戲地圖被抽象成網(wǎng)格或路點(diǎn)圖每個格子就是節(jié)點(diǎn)相鄰格子的移動消耗就是邊權(quán)。當(dāng)移動消耗取決于地形沼澤、山地、平原時Dijkstra和它的變種A就替代了BFS。A本質(zhì)是Dijkstra加了一個啟發(fā)函數(shù)比Dijkstra更快地導(dǎo)向目標(biāo)方向。物流和公共交通調(diào)度里也大量使用。我在一個配送路徑優(yōu)化的模擬項目里用Dijkstra計算倉庫到各個配送點(diǎn)的最短消耗路徑再配合線性規(guī)劃做車輛分配效果比單純手工規(guī)劃穩(wěn)定得多。6.2 學(xué)完Dijkstra下一步還能往哪走Dijkstra是進(jìn)入圖論算法的一個大門。學(xué)完它有幾個自然的進(jìn)階方向。第一個是Johnson算法。它組合了Bellman-Ford和Dijkstra用于解決帶負(fù)權(quán)邊的全源最短路徑問題?；舅悸肥窍茸鲆淮蜝ellman-Ford做勢能重標(biāo)定把所有邊權(quán)轉(zhuǎn)成非負(fù)再跑V次Dijkstra。在稀疏圖上這比Floyd快很多。第二個是層次圖最短路徑。有些問題把狀態(tài)擴(kuò)展成多層比如允許免費(fèi)一次的路徑規(guī)劃可以把每個節(jié)點(diǎn)拆成多個層層間建特定權(quán)值的邊再用Dijkstra跑。這種建圖技巧在競賽和企業(yè)面試?yán)锒冀?jīng)常出現(xiàn)。第三個是動態(tài)圖上的最短路徑。真實路網(wǎng)是動態(tài)變化的比如堵車導(dǎo)致某條邊權(quán)實時上漲。這時候跑全量Dijkstra很浪費(fèi)更好的做法是在原有計算結(jié)果上局部更新受影響區(qū)域。這個方向叫增量最短路徑工程價值很高。第四個是并行化。大規(guī)模圖的最短路徑可以用GPU并行加速每個迭代階段并行處理多個節(jié)點(diǎn)的松弛。比如在已經(jīng)擁有數(shù)億節(jié)點(diǎn)的社交網(wǎng)絡(luò)圖上計算接近中心性就必須考慮并行化的Dijkstra實現(xiàn)。學(xué)完這幾個方向最短路徑這個知識樹基本就完整了。7. 最后分享一點(diǎn)個人經(jīng)驗回到開頭那個問題一張圖、一個起點(diǎn)、若干帶權(quán)邊Dijkstra怎么用才最舒服我自己的習(xí)慣是每寫一個Dijkstra版本之前先問三個問題圖里有負(fù)權(quán)邊嗎圖是稠密還是稀疏需要路徑還原還是只要距離這三個問題的答案直接決定選哪個實現(xiàn)、建什么數(shù)據(jù)結(jié)構(gòu)、記錄哪些額外信息。大多數(shù)翻車都不是算法沒寫對而是沒答好這三問。動手驗證比看十遍講解都有效。我建議新手拿到任意一張小圖手動畫出來按Dijkstra的每輪選擇在紙上標(biāo)一遍強(qiáng)烈推薦配合打印每個輪次的dist數(shù)組來觀察。你會看到貪心選擇如何一步步把臨時值變成最終值也會看到松弛操作如何反復(fù)糾正之前的粗略估算。有了這種手感再去寫代碼和debug會順暢很多。