現(xiàn)與工程實(shí)踐)
前陣子幫一個(gè)團(tuán)隊(duì)看園區(qū)導(dǎo)覽的小項(xiàng)目剛開始圖上只有幾十個(gè)點(diǎn)位最短路這塊完全沒人當(dāng)一回事。等數(shù)據(jù)源里的監(jiān)控點(diǎn)位一接進(jìn)來節(jié)點(diǎn)憑空多出六七倍原來那套直接全源預(yù)計(jì)算的方案開始卡頓這才有人跑來問我Dijkstra 和 Floyd 到底該怎么選。說實(shí)話這兩個(gè)名字在技術(shù)群里被問了無數(shù)次但真要在工程里給出一個(gè)讓自己滿意的答案遠(yuǎn)不是背個(gè)模板那么簡單。這篇就以最短路算法里最容易碰到的這兩塊內(nèi)容為主線把原理、實(shí)現(xiàn)、選型、坑點(diǎn)串一遍。適合正在學(xué)圖論的初學(xué)者也適合準(zhǔn)備算法面試或者正在寫路徑規(guī)劃 Demo 的開發(fā)者。1. 先搞清楚兩個(gè)算法各自適合什么場景1.1 給最短路問題劃定一個(gè)明確邊界在聊算法之前先把問題本身說清楚。給定一張有向圖圖里有節(jié)點(diǎn)和帶權(quán)邊權(quán)重表示從一個(gè)節(jié)點(diǎn)走到另一個(gè)節(jié)點(diǎn)的代價(jià)最短路問題就是找一條從起點(diǎn)到終點(diǎn)、邊權(quán)之和最小的路徑。工程里最常見的兩種變形是單源最短路也就是給定一個(gè)起點(diǎn)求它到所有其他點(diǎn)的最短距離另一種是全源最短路要求圖中任意兩點(diǎn)之間的最短距離和對(duì)應(yīng)路徑。這里有一個(gè)關(guān)鍵前提必須分清楚討論 Dijkstra 時(shí)默認(rèn)所有邊權(quán)都是非負(fù)數(shù)因?yàn)檫@是 Dijkstra 貪心策略成立的核心條件。Floyd 則稍微寬松一些能處理沒有負(fù)環(huán)的負(fù)權(quán)邊。所謂負(fù)環(huán)就是圖中存在一個(gè)環(huán)繞一圈的總權(quán)重還是負(fù)數(shù)這種情況下最短路徑?jīng)]有下界任何算法都無法給出有限的答案。先約定記號(hào)n 表示節(jié)點(diǎn)數(shù)m 表示邊數(shù)。Dijkstra 的堆優(yōu)化復(fù)雜度通常寫成 O((nm)log n)Floyd 的復(fù)雜度則是穩(wěn)定的 O(n^3)。也就是說當(dāng) n 大到幾百幾千時(shí)Floyd 和 Dijkstra 的差距會(huì)呈現(xiàn)數(shù)量級(jí)的差別后面會(huì)專門用實(shí)例說明。1.2 Dijkstra 為什么快貪心鎖點(diǎn)的邏輯Dijkstra 的核心思路可以概括成一句話每次從未確定的點(diǎn)里挑一個(gè)當(dāng)前距離最小的點(diǎn)把它“鎖死”然后用它去更新相鄰點(diǎn)。為什么敢“鎖死”我們用一個(gè)生活化的比喻來解釋。假設(shè)你站在起點(diǎn)每個(gè)點(diǎn)的當(dāng)前距離就是“已知的到該點(diǎn)最短試探距離”。既然所有邊權(quán)非負(fù)那么從起點(diǎn)出發(fā)任何一條繞路到達(dá)當(dāng)前最小距離點(diǎn) u 的路徑都必須先經(jīng)過某個(gè)距離不小于 u 的點(diǎn)繞路本身只會(huì)讓路徑更長。因此當(dāng)前距離最小的點(diǎn) u不可能再通過其他點(diǎn)繞出一條更短的路徑它此刻的距離就是真正的最終答案。這就是貪心算法的典型特征局部最優(yōu)的選擇能導(dǎo)出全局最優(yōu)。Dijkstra 每次選擇當(dāng)前距離最小的未訪問點(diǎn)并永久標(biāo)記它這個(gè)過程不斷重復(fù)直到所有可達(dá)點(diǎn)都被鎖定。樸素實(shí)現(xiàn)的尋找最小點(diǎn)需要 O(n) 掃描整個(gè)算法為 O(n^2)使用優(yōu)先隊(duì)列后尋找最小點(diǎn)的時(shí)間降為 O(log n)總復(fù)雜度變?yōu)?O((nm)log n)。后面的完整實(shí)現(xiàn)部分會(huì)給出代碼但先記住這個(gè)“鎖點(diǎn)”直覺調(diào)試時(shí)遇到問題會(huì)更容易定位。1.3 Floyd 為什么簡單三維 DP 的降維思維Floyd 的代碼量很少通常十幾行就能寫完但網(wǎng)上關(guān)于“k 為什么必須寫在外層”的問題層出不窮。理解了它的原理這些問題就不存在了。Floyd 本質(zhì)上是一個(gè)動(dòng)態(tài)規(guī)劃過程。定義 f[k][i][j] 表示“只允許使用編號(hào)小于等于 k 的節(jié)點(diǎn)作為中間節(jié)點(diǎn)時(shí)i 到 j 的最短距離”。動(dòng)態(tài)規(guī)劃轉(zhuǎn)移方程是f[k][i][j] min( f[k-1][i][j], f[k-1][i][k] f[k-1][k][j] )含義很直接從 i 到 j要么不經(jīng)過新加入的節(jié)點(diǎn) k路徑還走原來的老路要么經(jīng)過 k那就從 i 先到 k再從 k 到 j。因?yàn)?k 的加入是逐步擴(kuò)大的這個(gè)轉(zhuǎn)移天然保證了完整性。實(shí)際寫代碼時(shí)k 這一維可以滾動(dòng)掉二維矩陣直接原地更新于是變成d[i][j] min(d[i][j], d[i][k] d[k][j])這也解釋了為什么 k 必須放在最外層。如果 k 放在內(nèi)層就相當(dāng)于在某一個(gè) i、j 的循環(huán)體內(nèi)部同時(shí)使用不同“層級(jí)”的 k 值狀態(tài)的先后順序被打亂結(jié)果必然錯(cuò)誤。Floyd 能處理負(fù)權(quán)邊是因?yàn)槊恳惠?k 的迭代都是一次全局修正負(fù)權(quán)邊帶來的影響會(huì)在后續(xù)輪次被矯正。但一旦存在負(fù)環(huán)每繞一圈距離更小最短路就沒有了有限答案。1.4 一張表做出工程選型實(shí)際項(xiàng)目里很少有人會(huì)把所有最短路算法都實(shí)現(xiàn)一遍通常是先根據(jù)場景篩選。我把常見場景整理成下面這張表場景邊權(quán)條件推薦算法復(fù)雜度單源最短路非負(fù)權(quán)Dijkstra 堆優(yōu)化O((nm)log n)單源最短路存在負(fù)權(quán)但無負(fù)環(huán)Bellman-Ford 或 SPFAO(nm)SPFA 平均更好全源最短路n 較小幾百以內(nèi)FloydO(n^3)全源最短路n 較大、圖稀疏跑 n 次 DijkstraO(n(nm)log n)全源最短路存在負(fù)權(quán)Johnson 算法O(nm n(nm)log n)看到這張表很多讀者會(huì)問全源最短路為什么不用 Floyd 一把梭答案是當(dāng) n 超過 500 或 1000 時(shí)n^3 的增長非?？鋸?。假設(shè) n1000Floyd 要做十億次級(jí)別的松弛操作而如果圖稀疏、m 只有幾千跑 n 次堆優(yōu)化的 Dijkstra 只要幾百萬次操作差距是兩個(gè)數(shù)量級(jí)以上。反過來如果 n 很小比如幾十Floyd 寫起來最省事還天然記錄了所有點(diǎn)對(duì)距離工程上非常舒服。2. 手寫 Dijkstra從樸素到堆優(yōu)化每一步都不白走2.1 數(shù)據(jù)結(jié)構(gòu)先定好鄰接表怎么選Dijkstra 的實(shí)現(xiàn)細(xì)節(jié)里圖的存儲(chǔ)方式是第一步。鄰接矩陣的優(yōu)點(diǎn)是隨機(jī)訪問任意兩點(diǎn)的邊權(quán)是 O(1)但空間是 O(n^2)。n 一旦到 10 萬鄰接矩陣直接爆內(nèi)存就算 n 只有幾千在很多內(nèi)存受限的場景也不劃算。鄰接表只存實(shí)際存在的邊空間 O(nm)對(duì)堆優(yōu)化版本來說更重要我們每次從堆頂彈出節(jié)點(diǎn) u需要快速遍歷 u 的所有出邊鄰接表天然支持這種操作。工程上我習(xí)慣用數(shù)組 結(jié)構(gòu)體的方式或者直接用 vector 存邊python 場景則用 list of dict。C 里常用這樣一段struct Edge { int to; int w; }; vectorEdge graph[MAXN];存無向圖的時(shí)候每條邊要加入兩次有向圖只需要一次。輸入數(shù)據(jù)如果可能給出重邊要保留最小的那條因?yàn)槎鄺l同向邊疊加后只有權(quán)重最小的對(duì)最短路有貢獻(xiàn)。2.2 樸素 Dijkstra 完整實(shí)現(xiàn)先給出樸素的 O(n^2) 版本。它代碼簡單、不容易寫錯(cuò)在稠密圖里甚至常常比堆優(yōu)化更快因?yàn)槌砻軋D里堆的 log n 常數(shù)也不容忽視。const int MAXN 1005; const int INF 0x3f3f3f3f; int dist[MAXN]; bool used[MAXN]; vectorEdge graph[MAXN]; void dijkstra_naive(int s, int n) { fill(dist, dist n 1, INF); memset(used, 0, sizeof(used)); dist[s] 0; for (int i 1; i n; i) { int u -1; int best INF; // 找當(dāng)前距離最小的未訪問點(diǎn) for (int v 1; v n; v) { if (!used[v] dist[v] best) { best dist[v]; u v; } } if (u -1) break; // 剩下的點(diǎn)都不可達(dá) used[u] true; // 用 u 松弛鄰居 for (auto e : graph[u]) { if (dist[e.to] dist[u] e.w) { dist[e.to] dist[u] e.w; } } } }這里的 used 數(shù)組就是前文說的“鎖點(diǎn)”。每次找最小點(diǎn)時(shí)掃描全部節(jié)點(diǎn)所以復(fù)雜度是 O(n^2)。注意初始化時(shí) i 從 1 到 n節(jié)點(diǎn)編號(hào)按 1 開始如果節(jié)點(diǎn)從 0 開始相應(yīng)地改成 0 到 n-1。提示如果圖是稠密圖n 只有幾百幾千且 m 接近 n^2樸素版往往比堆優(yōu)化版還快。因?yàn)槎褍?yōu)化的常數(shù)開銷在這種規(guī)模下可能超過 O(n^2) 的掃描成本。很多算法模板只教堆優(yōu)化容易讓人誤以為樸素版沒意義其實(shí)它非常適合稠密小圖。2.3 優(yōu)先隊(duì)列優(yōu)化版本當(dāng) n 在 10 萬級(jí)別、圖又稀疏的時(shí)候樸素版每一次掃描都是災(zāi)難必須用堆來維護(hù)當(dāng)前距離最小的點(diǎn)。C 的 priority_queue 默認(rèn)是大頂堆所以要用 pair 或者自定義比較器。常見寫法是把距離的相反數(shù)放進(jìn)去或者用 greater 指定小頂堆。下面是完整模板const int MAXN 100005; const int INF 0x3f3f3f3f; vectorEdge graph[MAXN]; int dist[MAXN]; bool vis[MAXN]; void dijkstra_heap(int s, int n) { fill(dist, dist n 1, INF); memset(vis, 0, sizeof(vis)); dist[s] 0; priority_queuepairint, int, vectorpairint, int, greaterpairint, int pq; pq.push({0, s}); while (!pq.empty()) { auto [d, u] pq.top(); pq.pop(); // 跳過已經(jīng)確定最短路的點(diǎn) if (vis[u]) continue; vis[u] true; // 如果不用 vis也可以用 if (d ! dist[u]) continue; for (auto e : graph[u]) { if (dist[e.to] dist[u] e.w) { dist[e.to] dist[u] e.w; pq.push({dist[e.to], e.to}); } } } }先解釋 pair 的排序邏輯。priority_queue 默認(rèn)按 pair 的第一個(gè)元素排序first 是距離所以堆頂總是距離最小的那個(gè)。greater 只是把默認(rèn)的大頂堆翻轉(zhuǎn)成小頂堆。節(jié)點(diǎn)一旦被更新我們就把新的距離和節(jié)點(diǎn)編號(hào)再次 push 進(jìn)堆因此堆里可能存在同一個(gè)節(jié)點(diǎn)的多個(gè)舊條目。每次彈出時(shí)通過 vis 判斷這個(gè)節(jié)點(diǎn)是否已經(jīng)確定了最終最短路是則跳過。這個(gè)“跳過舊條目”是關(guān)鍵細(xì)節(jié)下面專門展開。為什么 vis[u] continue 不會(huì)導(dǎo)致漏更新因?yàn)楫?dāng) u 第一次以當(dāng)前最短距離從堆頂彈出時(shí)貪心性質(zhì)保證它已經(jīng)不可能再被其他點(diǎn)更新后續(xù)所有相同節(jié)點(diǎn)的條目都是冗余的。所以先彈出先鎖定后面重復(fù)彈出直接忽略。如果寫成 if (d ! dist[u]) continue效果一樣因?yàn)?d 不是最新距離說明這條記錄已經(jīng)過期。從復(fù)雜度角度看每條邊最多觸發(fā)一次成功的松弛每次成功松弛都會(huì)向堆里 push 一次堆至多 O(m) 條記錄每次 pop 是 O(log m)總復(fù)雜度 O((nm)log n)。2.4 順手把最短路徑也打出來實(shí)際項(xiàng)目中不能只返回距離很多場景需要路徑本身。Dijkstra 記錄路徑的思路很簡單更新 dist[e.to] 時(shí)把 prev[e.to] 設(shè)置為 u。最終從終點(diǎn)反向追溯 prev 就能得到路徑。打印時(shí)用一個(gè)?；蛘哌f歸逆序輸出。示例代碼如下int prev_node[MAXN]; void dijkstra_with_path(int s, int n) { // dist, vis 初始化同上 memset(prev_node, 0, sizeof(prev_node)); while (!pq.empty()) { auto [d, u] pq.top(); pq.pop(); if (vis[u]) continue; vis[u] true; for (auto e : graph[u]) { if (dist[e.to] dist[u] e.w) { dist[e.to] dist[u] e.w; prev_node[e.to] u; pq.push({dist[e.to], e.to}); } } } } void print_path(int s, int t) { if (dist[t] INF) { cout 不可達(dá) endl; return; } vectorint path; for (int v t; v ! 0; v prev_node[v]) { path.push_back(v); } reverse(path.begin(), path.end()); for (int i 0; i path.size(); i) { if (i) cout - ; cout path[i]; } cout endl; }注意 prev 數(shù)組初始化為 0表示沒有前驅(qū)。起點(diǎn) s 的 prev 保持 0所以回溯到 0 時(shí)停止。這個(gè)方法對(duì)路徑記錄要求不高的小圖完全夠用。3. Floyd 十行代碼背后的幾個(gè)坑3.1 k 必須在外層很多人栽在這里Floyd 的代碼極簡單寫錯(cuò)了也不容易一眼發(fā)現(xiàn)因?yàn)樗鼈儾粫?huì)直接報(bào)錯(cuò)而是給出一個(gè)偏大的錯(cuò)誤結(jié)果。最典型的問題就是三重循環(huán)的嵌套順序。正確順序是 k 在外層i 和 j 在內(nèi)層。前面講原理時(shí)說過k 每一輪代表“允許使用新加入的節(jié)點(diǎn)作為中間節(jié)點(diǎn)”這個(gè)順序是狀態(tài)轉(zhuǎn)移過程的核心。如果寫反了比如把 k 放在最內(nèi)層那么對(duì)于一對(duì) i、j會(huì)在同一個(gè) i、j 循環(huán)里連續(xù)嘗試所有 k。這種做法完全沒有狀態(tài)累計(jì)當(dāng)你第一次嘗試 k1 時(shí)還沒更新任何結(jié)果下一次嘗試 k2 時(shí)也沒有把 k1 的結(jié)果納入進(jìn)去。最終 bug 的表現(xiàn)通常是距離沒更新夠路徑明顯繞遠(yuǎn)或者在某些不可達(dá)的節(jié)點(diǎn)之間給出了不合理的值。我見過最有效的檢查方法是用三重循環(huán)順序的三層含義來幫助記憶最外層 k 代表“決策中間節(jié)點(diǎn)的編號(hào)上限”內(nèi)層 i、j 則是在這個(gè)限制背景下枚舉所有起點(diǎn)和終點(diǎn)。直接背 i、j、k 的順序容易錯(cuò)背語義就不會(huì)踩坑。3.2 順手把路徑也記錄下來Floyd 的路徑重建比 Dijkstra 稍微繞一點(diǎn)。常見的辦法是開一個(gè) next[i][j] 數(shù)組表示從 i 到 j 的最短路徑上i 的下一個(gè)節(jié)點(diǎn)是誰。初始化時(shí)對(duì)于每一條有向邊 i-jnext[i][j] j沒有邊的則默認(rèn)保持 j 或 0。在松弛成功時(shí)更新 nextif (d[i][k] d[k][j] d[i][j]) { d[i][j] d[i][k] d[k][j]; next[i][j] next[i][k]; }這里如果想當(dāng)然寫成 next[i][j] k就錯(cuò)了。因?yàn)?i 到 k 的最短路徑可能已經(jīng)經(jīng)過了其他中間節(jié)點(diǎn)i 走向這個(gè)新路徑上的第一個(gè)節(jié)點(diǎn)不一定是 k而是 next[i][k]。只有記錄 next[i][k]才能完整還原路徑。打印路徑時(shí)只需要從 next[i][j] 出發(fā)不斷跳轉(zhuǎn)void print_floyd_path(int u, int v) { if (d[u][v] INF) { printf(不可達(dá)\n); return; } printf(%d, u); while (u ! v) { u next[u][v]; printf( - %d, u); } printf(\n); }3.3 初始化、重邊、自環(huán)三個(gè)習(xí)慣一次養(yǎng)成Floyd 的初始化往往決定成敗。首先把整個(gè)矩陣 d[i][j] 初始化為 INF再把 d[i][i] 初始化為 0。接下來讀入邊。輸入如果出現(xiàn)重邊要取最小值自環(huán)即 i 到 i 的邊在非負(fù)權(quán)場景下不會(huì)對(duì)最短路有正面貢獻(xiàn)可以忽略但如果存在負(fù)權(quán)自環(huán)那就相當(dāng)于負(fù)環(huán)問題整個(gè)最短路都不成立通常需要單獨(dú)排查。INF 的選擇也要小心。很多人直接用 int 的 INT_MAX然后判斷 d[i][k] d[k][j] d[i][j]一旦 d[i][k] 和 d[k][j] 都是 INF兩者相加直接溢出變成負(fù)數(shù)導(dǎo)致錯(cuò)誤更新。我在工程里習(xí)慣用 0x3f3f3f3f這個(gè)值約等于十億兩個(gè)相加也不會(huì)溢出 32 位 int同時(shí)還能繼續(xù)滿足“比任何真實(shí)路徑都大”的需求。更好的習(xí)慣是松弛時(shí)顯式判斷if (d[i][k] ! INF d[k][j] ! INF) { if (d[i][k] d[k][j] d[i][j]) { d[i][j] d[i][k] d[k][j]; } }這樣寫雖然多兩行但能避免所有溢出的心智負(fù)擔(dān)。數(shù)據(jù)范圍較大、邊權(quán)可能達(dá)到 10^9 時(shí)把 dist 數(shù)組的類型改成 long long判斷邏輯不變。4. 真實(shí)案例復(fù)盤一個(gè)導(dǎo)覽項(xiàng)目里的最短路選型4.1 一個(gè)再常見不過的場景前文提到的園區(qū)導(dǎo)覽項(xiàng)目最初的模型很簡單幾十個(gè)展覽點(diǎn)位作為圖節(jié)點(diǎn)點(diǎn)與點(diǎn)之間的步行路線作為邊游客想去任意兩個(gè)點(diǎn)位之間系統(tǒng)需要給出最短步行路線和距離。當(dāng)時(shí)節(jié)點(diǎn)少Floyd 一次預(yù)計(jì)算全部點(diǎn)對(duì)之后再查詢都是 O(1) 查表完全沒問題。后來團(tuán)隊(duì)把監(jiān)控點(diǎn)位、商店、洗手間等大量新節(jié)點(diǎn)都并入了同一張圖節(jié)點(diǎn)數(shù)從 30 漲到 700 多邊數(shù)接近 2000圖仍然很稀疏。Floyd 的預(yù)計(jì)算開始變成瓶頸在純 Python 的調(diào)試腳本里700^3 大約三億多次操作肉眼可見地卡頓。更重要的是后續(xù)還希望支持動(dòng)態(tài)修改某些邊權(quán)每次修改如果都重跑全源 Floyd體驗(yàn)會(huì)非常差。這個(gè)時(shí)候真正需要權(quán)衡的問題就變成了查詢頻率高不高圖會(huì)不會(huì)頻繁更新如果只是偶爾算一次全量數(shù)據(jù)Floyd 其實(shí)也能接受但如果是頻繁的單點(diǎn)查詢并且圖規(guī)模不小Dijkstra 明顯是更穩(wěn)的選擇。4.2 性能對(duì)比與實(shí)測印象為了說清楚這個(gè)問題我在項(xiàng)目里用隨機(jī)生成的 600 個(gè)節(jié)點(diǎn)、1800 條邊的稀疏圖做過一個(gè)簡單對(duì)比。理論復(fù)雜度如下算法復(fù)雜度n600, m1800預(yù)估操作規(guī)模樸素 Dijkstra 單源O(n^2m)約 36 萬次堆優(yōu)化 Dijkstra 單源O((nm)log n)約 1.6 萬次Floyd 全源O(n^3)約 2.16 億次可以看到單源 Dijkstra 和全源 Floyd 差了好幾個(gè)數(shù)量級(jí)。實(shí)際跑起來C 編譯優(yōu)化后的結(jié)果更明顯堆優(yōu)化 Dijkstra 完成一次單源計(jì)算在毫秒級(jí)Floyd 跑完全源需要零點(diǎn)幾秒而純 Python 的三重循環(huán)要慢得多交互式查詢時(shí)卡頓感非常強(qiáng)。所以最終核心模塊用 C 重寫每個(gè)游客查詢時(shí)按需跑一次 Dijkstra只計(jì)算需要的那個(gè)終點(diǎn)路徑返回也順手。這里有個(gè)工程心得如果系統(tǒng)需要頻繁查詢“任意兩點(diǎn)”且圖節(jié)點(diǎn)少于 200Floyd 的預(yù)計(jì)算模式非常舒服查詢 O(1)代碼簡單一旦節(jié)點(diǎn)上了 500就要認(rèn)真考慮改成“每次查詢跑 Dijkstra”或者“按熱點(diǎn)區(qū)域做預(yù)計(jì)算”。選型不是背復(fù)雜度公式而是理解自己系統(tǒng)中的查詢比例和更新頻率。4.3 落地時(shí)的幾個(gè)代碼細(xì)節(jié)實(shí)際落地時(shí)除了算法本身還要處理幾個(gè)工程細(xì)節(jié)。第一圖的存儲(chǔ)從鄰接矩陣換成了鄰接表因?yàn)?700 個(gè)節(jié)點(diǎn)的鄰接矩陣是 49 萬格雖然內(nèi)存上不算大但遍歷出邊時(shí)鄰接表快得多。第二輸出路徑時(shí)統(tǒng)一封裝成接口前端只拿節(jié)點(diǎn)序列和總距離不關(guān)心內(nèi)部是 Dijkstra 還是查表方便日后替換。第三因?yàn)閳D數(shù)據(jù)來自多個(gè)信息源重邊幾乎必然存在讀入階段統(tǒng)一取最小值否則 Dijkstra 會(huì)被無關(guān)重邊干擾。這里還要提醒一點(diǎn)最短路算法只是路徑服務(wù)的一環(huán)真實(shí)系統(tǒng)里往往還涉及禁行路段、步行耗時(shí)估計(jì)、逗留時(shí)長等業(yè)務(wù)規(guī)則。我習(xí)慣在算法層之上做一層“路網(wǎng)服務(wù)”把最短路計(jì)算和業(yè)務(wù)規(guī)則解耦這樣算法升級(jí)或替換時(shí)上層完全不用改。5. 常見問題與排查技巧實(shí)錄5.1 隊(duì)列里全是舊數(shù)據(jù)你被坑過一次就懂了堆優(yōu)化 Dijkstra 最常見的問題就是忘記處理堆里的“過期數(shù)據(jù)”?，F(xiàn)象是某些節(jié)點(diǎn)的 dist 偏大或偏小程序在隨機(jī)數(shù)據(jù)上偶爾正確一旦圖復(fù)雜一點(diǎn)就全亂。原因很多新手分析不出來。事實(shí)上每次 dist[e.to] 被更新時(shí)我們都會(huì)往堆里 push 一個(gè)全新的 pair同一個(gè)節(jié)點(diǎn)可能在堆里同時(shí)存在多個(gè)不同距離的記錄。如果不對(duì)過期記錄做任何判斷程序就可能把一條已經(jīng)過期的舊距離當(dāng)成當(dāng)前距離來松弛鄰居。舉例來說某個(gè)節(jié)點(diǎn)先被一條較長的路徑更新入堆后來又發(fā)現(xiàn)更短的路徑再入堆。堆頂彈出的應(yīng)該是更短的那條但如果代碼沒有跳過舊記錄它可能用舊距離繼續(xù)更新鄰居算出來的結(jié)果就不是最優(yōu)。修復(fù)方式就是前面代碼中的 vis 標(biāo)記或 if (d ! dist[u]) continue。從工程角度寫 Dijkstra 時(shí)最好一開始就把跳過過期記錄的代碼寫進(jìn)去。這行代碼不是可選項(xiàng)而是正確性的必要條件。5.2 負(fù)數(shù)權(quán)邊的反直覺案例有一個(gè)經(jīng)典反例可以瞬間擊碎對(duì) Dijkstra 的盲目信任。假設(shè)起點(diǎn)是 s存在 s-a 邊權(quán) 5s-b 邊權(quán) 6b-a 邊權(quán) -2。直觀上s 到 a 的最短距離是走 s-b-a路程 4但 Dijkstra 一開始會(huì)選擇從 s 出發(fā)距離更小的 a直接鎖定 5然后才處理 b。最終它輸出的 s 到 a 的距離是 5而正確答案是 4。原因在于 Dijkstra 鎖點(diǎn)依賴的是“繞路不會(huì)更短”的性質(zhì)而負(fù)權(quán)邊徹底破壞了這一點(diǎn)繞路雖然經(jīng)過更遠(yuǎn)的點(diǎn)但負(fù)權(quán)可能把總代價(jià)拉回更低。所以只要輸入里有負(fù)權(quán)邊Dijkstra 就必須徹底換掉改用 Bellman-Ford 或 SPFA。Floyd 可以處理單個(gè)負(fù)權(quán)邊但對(duì)負(fù)環(huán)無能為力。遇到負(fù)權(quán)先想想問題本身是否合法再進(jìn)行算法選型。5.3 越界與溢出的隱蔽 Bug最短路代碼里最隱蔽的錯(cuò)誤不是邏輯混亂而是 INF 加法溢出。當(dāng) INF 取 INT_MAX且兩個(gè)不可達(dá)節(jié)點(diǎn)的距離相加時(shí)結(jié)果溢出成負(fù)數(shù)程序反而認(rèn)為它是一條更短路徑。這種事在 Floyd 的樸素寫法和 Dijkstra 的比較條件里都可能出現(xiàn)。我推薦的防御姿勢有兩個(gè)。第一個(gè)是 INF 用 0x3f3f3f3f保證 INF INF 不溢出第二個(gè)是寫比較時(shí)拆開判斷像前面 Floyd 初始化那節(jié)寫的一樣先判斷不等于 INF再做相加比較。如果數(shù)據(jù)范圍很大干脆把 dist 數(shù)組聲明為 long long用 long long 的 INF比如 4e18徹底告別整數(shù)溢出問題。很多比賽選手習(xí)慣性地開 long long不是沒有道理的。5.4 怎么快速驗(yàn)證算法寫對(duì)了寫完之后怎么確認(rèn)實(shí)現(xiàn)正確單靠眼睛看代碼通常不夠。我最常用的方法是構(gòu)造小圖手算。找一個(gè)五六個(gè)節(jié)點(diǎn)的樣例把 dist 數(shù)組按輪次手推一遍跟程序輸出對(duì)比。這個(gè)過程不麻煩但能快速暴露初始化、循環(huán)順序、路徑輸出等細(xì)節(jié)問題。第二個(gè)方法是對(duì)拍。邊權(quán)全部設(shè)為 1 的圖Dijkstra 的結(jié)果應(yīng)該和 BFS 的層數(shù)完全一致用這段代碼對(duì)比很快。更通用的對(duì)拍是用 Floyd 驗(yàn)證 Dijkstra隨機(jī)生成一張小圖跑一遍 Dijkstra 得到單源最短路再跑一遍 Floyd 得到全源最短路比較特定起點(diǎn)的所有 dist 是否一致。如果兩者對(duì)不上說明其中某個(gè)實(shí)現(xiàn)有問題。由于 Floyd 結(jié)構(gòu)簡單通常默認(rèn)它是基準(zhǔn)。這個(gè)“暴力對(duì)拍”的思路在工程里也常用把新實(shí)現(xiàn)和線上基準(zhǔn)跑同一批數(shù)據(jù)用腳本自動(dòng)比對(duì)輸出能省下大量排查時(shí)間。6. 用不上的時(shí)候也要知道進(jìn)階方向6.1 有負(fù)權(quán)邊的全源場景如果一張圖既有負(fù)權(quán)邊又需要全源最短路直接跑 n 次 Dijkstra 是不行的因?yàn)?Dijkstra 根本不能處理負(fù)權(quán)。這時(shí)候可以了解一下 Johnson 算法它的思路非常經(jīng)典先跑一遍 Bellman-Ford 給每個(gè)節(jié)點(diǎn)算一個(gè)“勢能”然后用勢能重新調(diào)整所有邊的權(quán)重把所有邊權(quán)變成非負(fù)數(shù)最后再跑 n 次 Dijkstra。調(diào)整權(quán)重的方式是對(duì)于每條邊 u-v把實(shí)際權(quán)重變成 w h[u] - h[v]。這個(gè)變換的好處是最短路徑不會(huì)因?yàn)樽儞Q而改變因?yàn)槁窂缴系膭菽茼?xiàng)會(huì)前后抵消。工程中很少需要自己實(shí)現(xiàn) Johnson但理解它有助于建立完整的算法知識(shí)體系。面試中如果被問到“負(fù)權(quán)全源怎么處理”能說出 Johnson 的思路是很加分的。6.2 比 Dijkstra 更快帶上啟發(fā)式在路徑規(guī)劃場景中Dijkstra 在一個(gè)很大的圖上找單個(gè)目標(biāo)點(diǎn)時(shí)會(huì)把圖里大量無關(guān)區(qū)域都擴(kuò)展一遍。這個(gè)時(shí)候可以用 A* 算法它在 Dijkstra 的基礎(chǔ)上增加一個(gè)啟發(fā)式估計(jì) h(n)表示從當(dāng)前節(jié)點(diǎn) n 到目標(biāo)點(diǎn)的估算代價(jià)。只要 h(n) 不過度估計(jì)真實(shí)代價(jià)A* 就保證找到最優(yōu)路徑而且擴(kuò)展的節(jié)點(diǎn)數(shù)通常遠(yuǎn)小于 Dijkstra。Dijkstra 相當(dāng)于 h(n)0 的特例所以從 Dijkstra 遷移到 A* 的代碼成本非常低主要改動(dòng)只是把優(yōu)先隊(duì)列里的排序鍵從當(dāng)前距離變成當(dāng)前距離加啟發(fā)值。地圖導(dǎo)航、游戲?qū)ぢ防镒畛Ｒ姷淖龇ň褪?A* 配合柵格地圖這也是最短路算法的經(jīng)典應(yīng)用延伸。如果做的是實(shí)時(shí)路徑規(guī)劃A* 往往比單純堆優(yōu)化的 Dijkstra 實(shí)用得多。6.3 當(dāng)圖變成了動(dòng)態(tài)圖真實(shí)系統(tǒng)中幾乎沒有永遠(yuǎn)靜態(tài)的邊權(quán)。路況變化、場地臨時(shí)封閉、某個(gè)節(jié)點(diǎn)暫停開放都會(huì)讓之前的計(jì)算結(jié)果失效。最直接的做法是重新跑一遍算法但如果圖很大而且更新頻繁重復(fù)計(jì)算成本太高。這個(gè)方向上的常見策略包括局部更新、增量維護(hù)、或者把圖拆成區(qū)域預(yù)處理。最短路動(dòng)態(tài)更新的核心困難在于一條邊變化可能影響很多節(jié)點(diǎn)但通常影響范圍是局部的。工程上的一個(gè)簡單思路是先用舊結(jié)果判斷受影響的節(jié)點(diǎn)范圍再在局部重跑 Dijkstra。很多商業(yè)導(dǎo)航系統(tǒng)背后都有類似的增量計(jì)算邏輯但實(shí)現(xiàn)復(fù)雜度明顯高于靜態(tài)算法。日常開發(fā)中如果遇到動(dòng)態(tài)圖不要急著寫復(fù)雜的增量邏輯先評(píng)估更新頻率很多時(shí)候“重新跑一次”反而是最簡單也最穩(wěn)定的方案。我個(gè)人在實(shí)際項(xiàng)目里的體會(huì)是最短路算法看起來是圖論里的基礎(chǔ)題但真正用好的關(guān)鍵是知道每個(gè)算法的前提條件、復(fù)雜度數(shù)量級(jí)和最容易被忽視的細(xì)節(jié)。Dijkstra 的貪心鎖點(diǎn)、Floyd 的三層遞推都值得親手寫一遍、親手掉一次坑。如果你正在學(xué)習(xí)這塊我建議從一張六節(jié)點(diǎn)的小圖開始手動(dòng)推一遍 dist 數(shù)組再用代碼跑一遍最后把打印出來的路徑逐條讀一次。這個(gè)過程比背十個(gè)模板都有用。 最短路算法選型指南：Dijkstra與Floyd原理、實(shí)現(xiàn)與工程實(shí)踐
前陣子幫一個(gè)團(tuán)隊(duì)看園區(qū)導(dǎo)覽的小項(xiàng)目剛開始圖上只有幾十個(gè)點(diǎn)位最短路這塊完全沒人當(dāng)一回事。等數(shù)據(jù)源里的監(jiān)控點(diǎn)位一接進(jìn)來節(jié)點(diǎn)憑空多出六七倍原來那套直接全源預(yù)計(jì)算的方案開始卡頓這才有人跑來問我Dijkstra 和 Floyd 到底該怎么選。說實(shí)話這兩個(gè)名字在技術(shù)群里被問了無數(shù)次但真要在工程里給出一個(gè)讓自己滿意的答案遠(yuǎn)不是背個(gè)模板那么簡單。這篇就以最短路算法里最容易碰到的這兩塊內(nèi)容為主線把原理、實(shí)現(xiàn)、選型、坑點(diǎn)串一遍。適合正在學(xué)圖論的初學(xué)者也適合準(zhǔn)備算法面試或者正在寫路徑規(guī)劃 Demo 的開發(fā)者。1. 先搞清楚兩個(gè)算法各自適合什么場景1.1 給最短路問題劃定一個(gè)明確邊界在聊算法之前先把問題本身說清楚。給定一張有向圖圖里有節(jié)點(diǎn)和帶權(quán)邊權(quán)重表示從一個(gè)節(jié)點(diǎn)走到另一個(gè)節(jié)點(diǎn)的代價(jià)最短路問題就是找一條從起點(diǎn)到終點(diǎn)、邊權(quán)之和最小的路徑。工程里最常見的兩種變形是單源最短路也就是給定一個(gè)起點(diǎn)求它到所有其他點(diǎn)的最短距離另一種是全源最短路要求圖中任意兩點(diǎn)之間的最短距離和對(duì)應(yīng)路徑。這里有一個(gè)關(guān)鍵前提必須分清楚討論 Dijkstra 時(shí)默認(rèn)所有邊權(quán)都是非負(fù)數(shù)因?yàn)檫@是 Dijkstra 貪心策略成立的核心條件。Floyd 則稍微寬松一些能處理沒有負(fù)環(huán)的負(fù)權(quán)邊。所謂負(fù)環(huán)就是圖中存在一個(gè)環(huán)繞一圈的總權(quán)重還是負(fù)數(shù)這種情況下最短路徑?jīng)]有下界任何算法都無法給出有限的答案。先約定記號(hào)n 表示節(jié)點(diǎn)數(shù)m 表示邊數(shù)。Dijkstra 的堆優(yōu)化復(fù)雜度通常寫成 O((nm)log n)Floyd 的復(fù)雜度則是穩(wěn)定的 O(n^3)。也就是說當(dāng) n 大到幾百幾千時(shí)Floyd 和 Dijkstra 的差距會(huì)呈現(xiàn)數(shù)量級(jí)的差別后面會(huì)專門用實(shí)例說明。1.2 Dijkstra 為什么快貪心鎖點(diǎn)的邏輯Dijkstra 的核心思路可以概括成一句話每次從未確定的點(diǎn)里挑一個(gè)當(dāng)前距離最小的點(diǎn)把它“鎖死”然后用它去更新相鄰點(diǎn)。為什么敢“鎖死”我們用一個(gè)生活化的比喻來解釋。假設(shè)你站在起點(diǎn)每個(gè)點(diǎn)的當(dāng)前距離就是“已知的到該點(diǎn)最短試探距離”。既然所有邊權(quán)非負(fù)那么從起點(diǎn)出發(fā)任何一條繞路到達(dá)當(dāng)前最小距離點(diǎn) u 的路徑都必須先經(jīng)過某個(gè)距離不小于 u 的點(diǎn)繞路本身只會(huì)讓路徑更長。因此當(dāng)前距離最小的點(diǎn) u不可能再通過其他點(diǎn)繞出一條更短的路徑它此刻的距離就是真正的最終答案。這就是貪心算法的典型特征局部最優(yōu)的選擇能導(dǎo)出全局最優(yōu)。Dijkstra 每次選擇當(dāng)前距離最小的未訪問點(diǎn)并永久標(biāo)記它這個(gè)過程不斷重復(fù)直到所有可達(dá)點(diǎn)都被鎖定。樸素實(shí)現(xiàn)的尋找最小點(diǎn)需要 O(n) 掃描整個(gè)算法為 O(n^2)使用優(yōu)先隊(duì)列后尋找最小點(diǎn)的時(shí)間降為 O(log n)總復(fù)雜度變?yōu)?O((nm)log n)。后面的完整實(shí)現(xiàn)部分會(huì)給出代碼但先記住這個(gè)“鎖點(diǎn)”直覺調(diào)試時(shí)遇到問題會(huì)更容易定位。1.3 Floyd 為什么簡單三維 DP 的降維思維Floyd 的代碼量很少通常十幾行就能寫完但網(wǎng)上關(guān)于“k 為什么必須寫在外層”的問題層出不窮。理解了它的原理這些問題就不存在了。Floyd 本質(zhì)上是一個(gè)動(dòng)態(tài)規(guī)劃過程。定義 f[k][i][j] 表示“只允許使用編號(hào)小于等于 k 的節(jié)點(diǎn)作為中間節(jié)點(diǎn)時(shí)i 到 j 的最短距離”。動(dòng)態(tài)規(guī)劃轉(zhuǎn)移方程是f[k][i][j] min( f[k-1][i][j], f[k-1][i][k] f[k-1][k][j] )含義很直接從 i 到 j要么不經(jīng)過新加入的節(jié)點(diǎn) k路徑還走原來的老路要么經(jīng)過 k那就從 i 先到 k再從 k 到 j。因?yàn)?k 的加入是逐步擴(kuò)大的這個(gè)轉(zhuǎn)移天然保證了完整性。實(shí)際寫代碼時(shí)k 這一維可以滾動(dòng)掉二維矩陣直接原地更新于是變成d[i][j] min(d[i][j], d[i][k] d[k][j])這也解釋了為什么 k 必須放在最外層。如果 k 放在內(nèi)層就相當(dāng)于在某一個(gè) i、j 的循環(huán)體內(nèi)部同時(shí)使用不同“層級(jí)”的 k 值狀態(tài)的先后順序被打亂結(jié)果必然錯(cuò)誤。Floyd 能處理負(fù)權(quán)邊是因?yàn)槊恳惠?k 的迭代都是一次全局修正負(fù)權(quán)邊帶來的影響會(huì)在后續(xù)輪次被矯正。但一旦存在負(fù)環(huán)每繞一圈距離更小最短路就沒有了有限答案。1.4 一張表做出工程選型實(shí)際項(xiàng)目里很少有人會(huì)把所有最短路算法都實(shí)現(xiàn)一遍通常是先根據(jù)場景篩選。我把常見場景整理成下面這張表場景邊權(quán)條件推薦算法復(fù)雜度單源最短路非負(fù)權(quán)Dijkstra 堆優(yōu)化O((nm)log n)單源最短路存在負(fù)權(quán)但無負(fù)環(huán)Bellman-Ford 或 SPFAO(nm)SPFA 平均更好全源最短路n 較小幾百以內(nèi)FloydO(n^3)全源最短路n 較大、圖稀疏跑 n 次 DijkstraO(n(nm)log n)全源最短路存在負(fù)權(quán)Johnson 算法O(nm n(nm)log n)看到這張表很多讀者會(huì)問全源最短路為什么不用 Floyd 一把梭答案是當(dāng) n 超過 500 或 1000 時(shí)n^3 的增長非?？鋸?。假設(shè) n1000Floyd 要做十億次級(jí)別的松弛操作而如果圖稀疏、m 只有幾千跑 n 次堆優(yōu)化的 Dijkstra 只要幾百萬次操作差距是兩個(gè)數(shù)量級(jí)以上。反過來如果 n 很小比如幾十Floyd 寫起來最省事還天然記錄了所有點(diǎn)對(duì)距離工程上非常舒服。2. 手寫 Dijkstra從樸素到堆優(yōu)化每一步都不白走2.1 數(shù)據(jù)結(jié)構(gòu)先定好鄰接表怎么選Dijkstra 的實(shí)現(xiàn)細(xì)節(jié)里圖的存儲(chǔ)方式是第一步。鄰接矩陣的優(yōu)點(diǎn)是隨機(jī)訪問任意兩點(diǎn)的邊權(quán)是 O(1)但空間是 O(n^2)。n 一旦到 10 萬鄰接矩陣直接爆內(nèi)存就算 n 只有幾千在很多內(nèi)存受限的場景也不劃算。鄰接表只存實(shí)際存在的邊空間 O(nm)對(duì)堆優(yōu)化版本來說更重要我們每次從堆頂彈出節(jié)點(diǎn) u需要快速遍歷 u 的所有出邊鄰接表天然支持這種操作。工程上我習(xí)慣用數(shù)組 結(jié)構(gòu)體的方式或者直接用 vector 存邊python 場景則用 list of dict。C 里常用這樣一段struct Edge { int to; int w; }; vectorEdge graph[MAXN];存無向圖的時(shí)候每條邊要加入兩次有向圖只需要一次。輸入數(shù)據(jù)如果可能給出重邊要保留最小的那條因?yàn)槎鄺l同向邊疊加后只有權(quán)重最小的對(duì)最短路有貢獻(xiàn)。2.2 樸素 Dijkstra 完整實(shí)現(xiàn)先給出樸素的 O(n^2) 版本。它代碼簡單、不容易寫錯(cuò)在稠密圖里甚至常常比堆優(yōu)化更快因?yàn)槌砻軋D里堆的 log n 常數(shù)也不容忽視。const int MAXN 1005; const int INF 0x3f3f3f3f; int dist[MAXN]; bool used[MAXN]; vectorEdge graph[MAXN]; void dijkstra_naive(int s, int n) { fill(dist, dist n 1, INF); memset(used, 0, sizeof(used)); dist[s] 0; for (int i 1; i n; i) { int u -1; int best INF; // 找當(dāng)前距離最小的未訪問點(diǎn) for (int v 1; v n; v) { if (!used[v] dist[v] best) { best dist[v]; u v; } } if (u -1) break; // 剩下的點(diǎn)都不可達(dá) used[u] true; // 用 u 松弛鄰居 for (auto e : graph[u]) { if (dist[e.to] dist[u] e.w) { dist[e.to] dist[u] e.w; } } } }這里的 used 數(shù)組就是前文說的“鎖點(diǎn)”。每次找最小點(diǎn)時(shí)掃描全部節(jié)點(diǎn)所以復(fù)雜度是 O(n^2)。注意初始化時(shí) i 從 1 到 n節(jié)點(diǎn)編號(hào)按 1 開始如果節(jié)點(diǎn)從 0 開始相應(yīng)地改成 0 到 n-1。提示如果圖是稠密圖n 只有幾百幾千且 m 接近 n^2樸素版往往比堆優(yōu)化版還快。因?yàn)槎褍?yōu)化的常數(shù)開銷在這種規(guī)模下可能超過 O(n^2) 的掃描成本。很多算法模板只教堆優(yōu)化容易讓人誤以為樸素版沒意義其實(shí)它非常適合稠密小圖。2.3 優(yōu)先隊(duì)列優(yōu)化版本當(dāng) n 在 10 萬級(jí)別、圖又稀疏的時(shí)候樸素版每一次掃描都是災(zāi)難必須用堆來維護(hù)當(dāng)前距離最小的點(diǎn)。C 的 priority_queue 默認(rèn)是大頂堆所以要用 pair 或者自定義比較器。常見寫法是把距離的相反數(shù)放進(jìn)去或者用 greater 指定小頂堆。下面是完整模板const int MAXN 100005; const int INF 0x3f3f3f3f; vectorEdge graph[MAXN]; int dist[MAXN]; bool vis[MAXN]; void dijkstra_heap(int s, int n) { fill(dist, dist n 1, INF); memset(vis, 0, sizeof(vis)); dist[s] 0; priority_queuepairint, int, vectorpairint, int, greaterpairint, int pq; pq.push({0, s}); while (!pq.empty()) { auto [d, u] pq.top(); pq.pop(); // 跳過已經(jīng)確定最短路的點(diǎn) if (vis[u]) continue; vis[u] true; // 如果不用 vis也可以用 if (d ! dist[u]) continue; for (auto e : graph[u]) { if (dist[e.to] dist[u] e.w) { dist[e.to] dist[u] e.w; pq.push({dist[e.to], e.to}); } } } }先解釋 pair 的排序邏輯。priority_queue 默認(rèn)按 pair 的第一個(gè)元素排序first 是距離所以堆頂總是距離最小的那個(gè)。greater 只是把默認(rèn)的大頂堆翻轉(zhuǎn)成小頂堆。節(jié)點(diǎn)一旦被更新我們就把新的距離和節(jié)點(diǎn)編號(hào)再次 push 進(jìn)堆因此堆里可能存在同一個(gè)節(jié)點(diǎn)的多個(gè)舊條目。每次彈出時(shí)通過 vis 判斷這個(gè)節(jié)點(diǎn)是否已經(jīng)確定了最終最短路是則跳過。這個(gè)“跳過舊條目”是關(guān)鍵細(xì)節(jié)下面專門展開。為什么 vis[u] continue 不會(huì)導(dǎo)致漏更新因?yàn)楫?dāng) u 第一次以當(dāng)前最短距離從堆頂彈出時(shí)貪心性質(zhì)保證它已經(jīng)不可能再被其他點(diǎn)更新后續(xù)所有相同節(jié)點(diǎn)的條目都是冗余的。所以先彈出先鎖定后面重復(fù)彈出直接忽略。如果寫成 if (d ! dist[u]) continue效果一樣因?yàn)?d 不是最新距離說明這條記錄已經(jīng)過期。從復(fù)雜度角度看每條邊最多觸發(fā)一次成功的松弛每次成功松弛都會(huì)向堆里 push 一次堆至多 O(m) 條記錄每次 pop 是 O(log m)總復(fù)雜度 O((nm)log n)。2.4 順手把最短路徑也打出來實(shí)際項(xiàng)目中不能只返回距離很多場景需要路徑本身。Dijkstra 記錄路徑的思路很簡單更新 dist[e.to] 時(shí)把 prev[e.to] 設(shè)置為 u。最終從終點(diǎn)反向追溯 prev 就能得到路徑。打印時(shí)用一個(gè)?；蛘哌f歸逆序輸出。示例代碼如下int prev_node[MAXN]; void dijkstra_with_path(int s, int n) { // dist, vis 初始化同上 memset(prev_node, 0, sizeof(prev_node)); while (!pq.empty()) { auto [d, u] pq.top(); pq.pop(); if (vis[u]) continue; vis[u] true; for (auto e : graph[u]) { if (dist[e.to] dist[u] e.w) { dist[e.to] dist[u] e.w; prev_node[e.to] u; pq.push({dist[e.to], e.to}); } } } } void print_path(int s, int t) { if (dist[t] INF) { cout 不可達(dá) endl; return; } vectorint path; for (int v t; v ! 0; v prev_node[v]) { path.push_back(v); } reverse(path.begin(), path.end()); for (int i 0; i path.size(); i) { if (i) cout - ; cout path[i]; } cout endl; }注意 prev 數(shù)組初始化為 0表示沒有前驅(qū)。起點(diǎn) s 的 prev 保持 0所以回溯到 0 時(shí)停止。這個(gè)方法對(duì)路徑記錄要求不高的小圖完全夠用。3. Floyd 十行代碼背后的幾個(gè)坑3.1 k 必須在外層很多人栽在這里Floyd 的代碼極簡單寫錯(cuò)了也不容易一眼發(fā)現(xiàn)因?yàn)樗鼈儾粫?huì)直接報(bào)錯(cuò)而是給出一個(gè)偏大的錯(cuò)誤結(jié)果。最典型的問題就是三重循環(huán)的嵌套順序。正確順序是 k 在外層i 和 j 在內(nèi)層。前面講原理時(shí)說過k 每一輪代表“允許使用新加入的節(jié)點(diǎn)作為中間節(jié)點(diǎn)”這個(gè)順序是狀態(tài)轉(zhuǎn)移過程的核心。如果寫反了比如把 k 放在最內(nèi)層那么對(duì)于一對(duì) i、j會(huì)在同一個(gè) i、j 循環(huán)里連續(xù)嘗試所有 k。這種做法完全沒有狀態(tài)累計(jì)當(dāng)你第一次嘗試 k1 時(shí)還沒更新任何結(jié)果下一次嘗試 k2 時(shí)也沒有把 k1 的結(jié)果納入進(jìn)去。最終 bug 的表現(xiàn)通常是距離沒更新夠路徑明顯繞遠(yuǎn)或者在某些不可達(dá)的節(jié)點(diǎn)之間給出了不合理的值。我見過最有效的檢查方法是用三重循環(huán)順序的三層含義來幫助記憶最外層 k 代表“決策中間節(jié)點(diǎn)的編號(hào)上限”內(nèi)層 i、j 則是在這個(gè)限制背景下枚舉所有起點(diǎn)和終點(diǎn)。直接背 i、j、k 的順序容易錯(cuò)背語義就不會(huì)踩坑。3.2 順手把路徑也記錄下來Floyd 的路徑重建比 Dijkstra 稍微繞一點(diǎn)。常見的辦法是開一個(gè) next[i][j] 數(shù)組表示從 i 到 j 的最短路徑上i 的下一個(gè)節(jié)點(diǎn)是誰。初始化時(shí)對(duì)于每一條有向邊 i-jnext[i][j] j沒有邊的則默認(rèn)保持 j 或 0。在松弛成功時(shí)更新 nextif (d[i][k] d[k][j] d[i][j]) { d[i][j] d[i][k] d[k][j]; next[i][j] next[i][k]; }這里如果想當(dāng)然寫成 next[i][j] k就錯(cuò)了。因?yàn)?i 到 k 的最短路徑可能已經(jīng)經(jīng)過了其他中間節(jié)點(diǎn)i 走向這個(gè)新路徑上的第一個(gè)節(jié)點(diǎn)不一定是 k而是 next[i][k]。只有記錄 next[i][k]才能完整還原路徑。打印路徑時(shí)只需要從 next[i][j] 出發(fā)不斷跳轉(zhuǎn)void print_floyd_path(int u, int v) { if (d[u][v] INF) { printf(不可達(dá)\n); return; } printf(%d, u); while (u ! v) { u next[u][v]; printf( - %d, u); } printf(\n); }3.3 初始化、重邊、自環(huán)三個(gè)習(xí)慣一次養(yǎng)成Floyd 的初始化往往決定成敗。首先把整個(gè)矩陣 d[i][j] 初始化為 INF再把 d[i][i] 初始化為 0。接下來讀入邊。輸入如果出現(xiàn)重邊要取最小值自環(huán)即 i 到 i 的邊在非負(fù)權(quán)場景下不會(huì)對(duì)最短路有正面貢獻(xiàn)可以忽略但如果存在負(fù)權(quán)自環(huán)那就相當(dāng)于負(fù)環(huán)問題整個(gè)最短路都不成立通常需要單獨(dú)排查。INF 的選擇也要小心。很多人直接用 int 的 INT_MAX然后判斷 d[i][k] d[k][j] d[i][j]一旦 d[i][k] 和 d[k][j] 都是 INF兩者相加直接溢出變成負(fù)數(shù)導(dǎo)致錯(cuò)誤更新。我在工程里習(xí)慣用 0x3f3f3f3f這個(gè)值約等于十億兩個(gè)相加也不會(huì)溢出 32 位 int同時(shí)還能繼續(xù)滿足“比任何真實(shí)路徑都大”的需求。更好的習(xí)慣是松弛時(shí)顯式判斷if (d[i][k] ! INF d[k][j] ! INF) { if (d[i][k] d[k][j] d[i][j]) { d[i][j] d[i][k] d[k][j]; } }這樣寫雖然多兩行但能避免所有溢出的心智負(fù)擔(dān)。數(shù)據(jù)范圍較大、邊權(quán)可能達(dá)到 10^9 時(shí)把 dist 數(shù)組的類型改成 long long判斷邏輯不變。4. 真實(shí)案例復(fù)盤一個(gè)導(dǎo)覽項(xiàng)目里的最短路選型4.1 一個(gè)再常見不過的場景前文提到的園區(qū)導(dǎo)覽項(xiàng)目最初的模型很簡單幾十個(gè)展覽點(diǎn)位作為圖節(jié)點(diǎn)點(diǎn)與點(diǎn)之間的步行路線作為邊游客想去任意兩個(gè)點(diǎn)位之間系統(tǒng)需要給出最短步行路線和距離。當(dāng)時(shí)節(jié)點(diǎn)少Floyd 一次預(yù)計(jì)算全部點(diǎn)對(duì)之后再查詢都是 O(1) 查表完全沒問題。后來團(tuán)隊(duì)把監(jiān)控點(diǎn)位、商店、洗手間等大量新節(jié)點(diǎn)都并入了同一張圖節(jié)點(diǎn)數(shù)從 30 漲到 700 多邊數(shù)接近 2000圖仍然很稀疏。Floyd 的預(yù)計(jì)算開始變成瓶頸在純 Python 的調(diào)試腳本里700^3 大約三億多次操作肉眼可見地卡頓。更重要的是后續(xù)還希望支持動(dòng)態(tài)修改某些邊權(quán)每次修改如果都重跑全源 Floyd體驗(yàn)會(huì)非常差。這個(gè)時(shí)候真正需要權(quán)衡的問題就變成了查詢頻率高不高圖會(huì)不會(huì)頻繁更新如果只是偶爾算一次全量數(shù)據(jù)Floyd 其實(shí)也能接受但如果是頻繁的單點(diǎn)查詢并且圖規(guī)模不小Dijkstra 明顯是更穩(wěn)的選擇。4.2 性能對(duì)比與實(shí)測印象為了說清楚這個(gè)問題我在項(xiàng)目里用隨機(jī)生成的 600 個(gè)節(jié)點(diǎn)、1800 條邊的稀疏圖做過一個(gè)簡單對(duì)比。理論復(fù)雜度如下算法復(fù)雜度n600, m1800預(yù)估操作規(guī)模樸素 Dijkstra 單源O(n^2m)約 36 萬次堆優(yōu)化 Dijkstra 單源O((nm)log n)約 1.6 萬次Floyd 全源O(n^3)約 2.16 億次可以看到單源 Dijkstra 和全源 Floyd 差了好幾個(gè)數(shù)量級(jí)。實(shí)際跑起來C 編譯優(yōu)化后的結(jié)果更明顯堆優(yōu)化 Dijkstra 完成一次單源計(jì)算在毫秒級(jí)Floyd 跑完全源需要零點(diǎn)幾秒而純 Python 的三重循環(huán)要慢得多交互式查詢時(shí)卡頓感非常強(qiáng)。所以最終核心模塊用 C 重寫每個(gè)游客查詢時(shí)按需跑一次 Dijkstra只計(jì)算需要的那個(gè)終點(diǎn)路徑返回也順手。這里有個(gè)工程心得如果系統(tǒng)需要頻繁查詢“任意兩點(diǎn)”且圖節(jié)點(diǎn)少于 200Floyd 的預(yù)計(jì)算模式非常舒服查詢 O(1)代碼簡單一旦節(jié)點(diǎn)上了 500就要認(rèn)真考慮改成“每次查詢跑 Dijkstra”或者“按熱點(diǎn)區(qū)域做預(yù)計(jì)算”。選型不是背復(fù)雜度公式而是理解自己系統(tǒng)中的查詢比例和更新頻率。4.3 落地時(shí)的幾個(gè)代碼細(xì)節(jié)實(shí)際落地時(shí)除了算法本身還要處理幾個(gè)工程細(xì)節(jié)。第一圖的存儲(chǔ)從鄰接矩陣換成了鄰接表因?yàn)?700 個(gè)節(jié)點(diǎn)的鄰接矩陣是 49 萬格雖然內(nèi)存上不算大但遍歷出邊時(shí)鄰接表快得多。第二輸出路徑時(shí)統(tǒng)一封裝成接口前端只拿節(jié)點(diǎn)序列和總距離不關(guān)心內(nèi)部是 Dijkstra 還是查表方便日后替換。第三因?yàn)閳D數(shù)據(jù)來自多個(gè)信息源重邊幾乎必然存在讀入階段統(tǒng)一取最小值否則 Dijkstra 會(huì)被無關(guān)重邊干擾。這里還要提醒一點(diǎn)最短路算法只是路徑服務(wù)的一環(huán)真實(shí)系統(tǒng)里往往還涉及禁行路段、步行耗時(shí)估計(jì)、逗留時(shí)長等業(yè)務(wù)規(guī)則。我習(xí)慣在算法層之上做一層“路網(wǎng)服務(wù)”把最短路計(jì)算和業(yè)務(wù)規(guī)則解耦這樣算法升級(jí)或替換時(shí)上層完全不用改。5. 常見問題與排查技巧實(shí)錄5.1 隊(duì)列里全是舊數(shù)據(jù)你被坑過一次就懂了堆優(yōu)化 Dijkstra 最常見的問題就是忘記處理堆里的“過期數(shù)據(jù)”?，F(xiàn)象是某些節(jié)點(diǎn)的 dist 偏大或偏小程序在隨機(jī)數(shù)據(jù)上偶爾正確一旦圖復(fù)雜一點(diǎn)就全亂。原因很多新手分析不出來。事實(shí)上每次 dist[e.to] 被更新時(shí)我們都會(huì)往堆里 push 一個(gè)全新的 pair同一個(gè)節(jié)點(diǎn)可能在堆里同時(shí)存在多個(gè)不同距離的記錄。如果不對(duì)過期記錄做任何判斷程序就可能把一條已經(jīng)過期的舊距離當(dāng)成當(dāng)前距離來松弛鄰居。舉例來說某個(gè)節(jié)點(diǎn)先被一條較長的路徑更新入堆后來又發(fā)現(xiàn)更短的路徑再入堆。堆頂彈出的應(yīng)該是更短的那條但如果代碼沒有跳過舊記錄它可能用舊距離繼續(xù)更新鄰居算出來的結(jié)果就不是最優(yōu)。修復(fù)方式就是前面代碼中的 vis 標(biāo)記或 if (d ! dist[u]) continue。從工程角度寫 Dijkstra 時(shí)最好一開始就把跳過過期記錄的代碼寫進(jìn)去。這行代碼不是可選項(xiàng)而是正確性的必要條件。5.2 負(fù)數(shù)權(quán)邊的反直覺案例有一個(gè)經(jīng)典反例可以瞬間擊碎對(duì) Dijkstra 的盲目信任。假設(shè)起點(diǎn)是 s存在 s-a 邊權(quán) 5s-b 邊權(quán) 6b-a 邊權(quán) -2。直觀上s 到 a 的最短距離是走 s-b-a路程 4但 Dijkstra 一開始會(huì)選擇從 s 出發(fā)距離更小的 a直接鎖定 5然后才處理 b。最終它輸出的 s 到 a 的距離是 5而正確答案是 4。原因在于 Dijkstra 鎖點(diǎn)依賴的是“繞路不會(huì)更短”的性質(zhì)而負(fù)權(quán)邊徹底破壞了這一點(diǎn)繞路雖然經(jīng)過更遠(yuǎn)的點(diǎn)但負(fù)權(quán)可能把總代價(jià)拉回更低。所以只要輸入里有負(fù)權(quán)邊Dijkstra 就必須徹底換掉改用 Bellman-Ford 或 SPFA。Floyd 可以處理單個(gè)負(fù)權(quán)邊但對(duì)負(fù)環(huán)無能為力。遇到負(fù)權(quán)先想想問題本身是否合法再進(jìn)行算法選型。5.3 越界與溢出的隱蔽 Bug最短路代碼里最隱蔽的錯(cuò)誤不是邏輯混亂而是 INF 加法溢出。當(dāng) INF 取 INT_MAX且兩個(gè)不可達(dá)節(jié)點(diǎn)的距離相加時(shí)結(jié)果溢出成負(fù)數(shù)程序反而認(rèn)為它是一條更短路徑。這種事在 Floyd 的樸素寫法和 Dijkstra 的比較條件里都可能出現(xiàn)。我推薦的防御姿勢有兩個(gè)。第一個(gè)是 INF 用 0x3f3f3f3f保證 INF INF 不溢出第二個(gè)是寫比較時(shí)拆開判斷像前面 Floyd 初始化那節(jié)寫的一樣先判斷不等于 INF再做相加比較。如果數(shù)據(jù)范圍很大干脆把 dist 數(shù)組聲明為 long long用 long long 的 INF比如 4e18徹底告別整數(shù)溢出問題。很多比賽選手習(xí)慣性地開 long long不是沒有道理的。5.4 怎么快速驗(yàn)證算法寫對(duì)了寫完之后怎么確認(rèn)實(shí)現(xiàn)正確單靠眼睛看代碼通常不夠。我最常用的方法是構(gòu)造小圖手算。找一個(gè)五六個(gè)節(jié)點(diǎn)的樣例把 dist 數(shù)組按輪次手推一遍跟程序輸出對(duì)比。這個(gè)過程不麻煩但能快速暴露初始化、循環(huán)順序、路徑輸出等細(xì)節(jié)問題。第二個(gè)方法是對(duì)拍。邊權(quán)全部設(shè)為 1 的圖Dijkstra 的結(jié)果應(yīng)該和 BFS 的層數(shù)完全一致用這段代碼對(duì)比很快。更通用的對(duì)拍是用 Floyd 驗(yàn)證 Dijkstra隨機(jī)生成一張小圖跑一遍 Dijkstra 得到單源最短路再跑一遍 Floyd 得到全源最短路比較特定起點(diǎn)的所有 dist 是否一致。如果兩者對(duì)不上說明其中某個(gè)實(shí)現(xiàn)有問題。由于 Floyd 結(jié)構(gòu)簡單通常默認(rèn)它是基準(zhǔn)。這個(gè)“暴力對(duì)拍”的思路在工程里也常用把新實(shí)現(xiàn)和線上基準(zhǔn)跑同一批數(shù)據(jù)用腳本自動(dòng)比對(duì)輸出能省下大量排查時(shí)間。6. 用不上的時(shí)候也要知道進(jìn)階方向6.1 有負(fù)權(quán)邊的全源場景如果一張圖既有負(fù)權(quán)邊又需要全源最短路直接跑 n 次 Dijkstra 是不行的因?yàn)?Dijkstra 根本不能處理負(fù)權(quán)。這時(shí)候可以了解一下 Johnson 算法它的思路非常經(jīng)典先跑一遍 Bellman-Ford 給每個(gè)節(jié)點(diǎn)算一個(gè)“勢能”然后用勢能重新調(diào)整所有邊的權(quán)重把所有邊權(quán)變成非負(fù)數(shù)最后再跑 n 次 Dijkstra。調(diào)整權(quán)重的方式是對(duì)于每條邊 u-v把實(shí)際權(quán)重變成 w h[u] - h[v]。這個(gè)變換的好處是最短路徑不會(huì)因?yàn)樽儞Q而改變因?yàn)槁窂缴系膭菽茼?xiàng)會(huì)前后抵消。工程中很少需要自己實(shí)現(xiàn) Johnson但理解它有助于建立完整的算法知識(shí)體系。面試中如果被問到“負(fù)權(quán)全源怎么處理”能說出 Johnson 的思路是很加分的。6.2 比 Dijkstra 更快帶上啟發(fā)式在路徑規(guī)劃場景中Dijkstra 在一個(gè)很大的圖上找單個(gè)目標(biāo)點(diǎn)時(shí)會(huì)把圖里大量無關(guān)區(qū)域都擴(kuò)展一遍。這個(gè)時(shí)候可以用 A* 算法它在 Dijkstra 的基礎(chǔ)上增加一個(gè)啟發(fā)式估計(jì) h(n)表示從當(dāng)前節(jié)點(diǎn) n 到目標(biāo)點(diǎn)的估算代價(jià)。只要 h(n) 不過度估計(jì)真實(shí)代價(jià)A* 就保證找到最優(yōu)路徑而且擴(kuò)展的節(jié)點(diǎn)數(shù)通常遠(yuǎn)小于 Dijkstra。Dijkstra 相當(dāng)于 h(n)0 的特例所以從 Dijkstra 遷移到 A* 的代碼成本非常低主要改動(dòng)只是把優(yōu)先隊(duì)列里的排序鍵從當(dāng)前距離變成當(dāng)前距離加啟發(fā)值。地圖導(dǎo)航、游戲?qū)ぢ防镒畛Ｒ姷淖龇ň褪?A* 配合柵格地圖這也是最短路算法的經(jīng)典應(yīng)用延伸。如果做的是實(shí)時(shí)路徑規(guī)劃A* 往往比單純堆優(yōu)化的 Dijkstra 實(shí)用得多。6.3 當(dāng)圖變成了動(dòng)態(tài)圖真實(shí)系統(tǒng)中幾乎沒有永遠(yuǎn)靜態(tài)的邊權(quán)。路況變化、場地臨時(shí)封閉、某個(gè)節(jié)點(diǎn)暫停開放都會(huì)讓之前的計(jì)算結(jié)果失效。最直接的做法是重新跑一遍算法但如果圖很大而且更新頻繁重復(fù)計(jì)算成本太高。這個(gè)方向上的常見策略包括局部更新、增量維護(hù)、或者把圖拆成區(qū)域預(yù)處理。最短路動(dòng)態(tài)更新的核心困難在于一條邊變化可能影響很多節(jié)點(diǎn)但通常影響范圍是局部的。工程上的一個(gè)簡單思路是先用舊結(jié)果判斷受影響的節(jié)點(diǎn)范圍再在局部重跑 Dijkstra。很多商業(yè)導(dǎo)航系統(tǒng)背后都有類似的增量計(jì)算邏輯但實(shí)現(xiàn)復(fù)雜度明顯高于靜態(tài)算法。日常開發(fā)中如果遇到動(dòng)態(tài)圖不要急著寫復(fù)雜的增量邏輯先評(píng)估更新頻率很多時(shí)候“重新跑一次”反而是最簡單也最穩(wěn)定的方案。我個(gè)人在實(shí)際項(xiàng)目里的體會(huì)是最短路算法看起來是圖論里的基礎(chǔ)題但真正用好的關(guān)鍵是知道每個(gè)算法的前提條件、復(fù)雜度數(shù)量級(jí)和最容易被忽視的細(xì)節(jié)。Dijkstra 的貪心鎖點(diǎn)、Floyd 的三層遞推都值得親手寫一遍、親手掉一次坑。如果你正在學(xué)習(xí)這塊我建議從一張六節(jié)點(diǎn)的小圖開始手動(dòng)推一遍 dist 數(shù)組再用代碼跑一遍最后把打印出來的路徑逐條讀一次。這個(gè)過程比背十個(gè)模板都有用。