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