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