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