面試官說Dijkstra寫不出來就滾，我用2個循環讓他閉嘴

去年某大廠算法面，候選人卡在優先隊列（一種按優先級取元素的數據結構）的實現上，20分鐘沒調通。面試官換了個問法：「Bellman-Ford會嗎？」候選人搖頭。面試結束。

這道題本可以用兩個嵌套循環解決，復雜度從O(E log V)退到O(VE)，但能跑通。

最短路徑算法的選型，本質是約束條件的翻譯游戲。LeetCode的圖論題不會告訴你該用哪個算法，它只給你一堆條件：有權還是無權？單源還是全點對？有沒有負權邊？

讀懂這些條件，比會寫代碼更重要。

無權圖：BFS的領地

社交網絡的六度分隔、迷宮的最少步數、Word Ladder的單詞變換——這些場景的共同點是什么？每一步的代價恒定為1。

BFS（廣度優先搜索）在這種場景下是統治級的。它的核心機制是層級擴散：從起點出發，先訪問所有距離為1的節點，再訪問距離為2的，以此類推。第一次觸及某個節點時，走過的步數就是最短路徑。

很多題目會把圖藏起來。二維矩陣里每個格子是節點，相鄰移動是邊；Word Ladder里每個單詞是節點，單字符差異是邊。識別出這種隱式圖結構，是解題的第一步。

但BFS有個硬邊界：它不認識「權重」這個概念。一旦不同邊的代價不同，層級擴散的邏輯就崩塌了——你無法再用「第幾層」來等價于「最短距離」。

正權圖：Dijkstra的貪心陷阱

當道路有長短、航班有價格差異時，圖變成帶權圖。Dijkstra算法的直覺很樸素：總是先處理當前距離起點最近的節點，并假設這個距離不會再被優化。

這個假設成立的前提是：所有邊的權重為正。正權重保證了「繞路不可能更優」——任何額外的邊只會增加總成本，不會讓已經確定的最短路徑變得更短。

實現上，Dijkstra依賴優先隊列來動態獲取「當前最小距離節點」。堆的插入和提取操作讓復雜度控制在O(E log V)，其中E是邊數，V是節點數。

但優先隊列是面試中的高頻翻車點。數組實現是O(V2)，二叉堆是O(E log V)，斐波那契堆理論上更優但沒人真的寫。很多候選人卡在堆的調整邏輯上，邊界條件一多就崩。

負權邊：Dijkstra的死刑，Bellman-Ford的入場券

如果圖中存在負權邊，Dijkstra的貪心假設徹底失效。想象一條路徑：A→B成本100，B→C成本-200。Dijkstra可能先確定A→B的最短距離為100，但后續發現A→D→B→C的總成本是-50，之前確定的「最短」被推翻。

Bellman-Ford算法為此而生。它不貪心，而是迭代。核心操作叫「邊松弛」：對每條邊(u,v)，如果dist[u] + weight(u,v) < dist[v]，就更新dist[v]。

第一輪迭代，找到所有只經過1條邊的最短路徑；第二輪，找到最多經過2條邊的最短路徑；以此類推。n個節點的圖，最短路徑最多包含n-1條邊，因此需要n-1輪迭代。

復雜度是O(VE)，比Dijkstra慢，但實現極簡：兩個嵌套循環，外層V-1次，內層遍歷所有邊。不需要堆，不需要復雜數據結構。

更關鍵的是，Bellman-Ford能檢測負權環。如果第V輪迭代還能松弛成功，說明存在可以無限降低成本的環路——這在金融套利檢測等場景中是核心需求。

全點對：Floyd-Warshall的空間換時間

當問題要求「任意兩點間的最短距離」時，單源算法需要執行V次，總復雜度O(V3 log V)或O(V2E)。Floyd-Warshall用動態規劃一次性解決：dp[k][i][j]表示「只允許經過節點1到k作為中轉，i到j的最短距離」。

狀態轉移方程是經典的：dp[k][i][j] = min(dp[k-1][i][j], dp[k-1][i][k] + dp[k-1][k][j])。空間可以滾動優化到二維，最終形式是三重循環。

這個算法的優雅之處在于，它把「路徑」拆解為「是否經過某個中轉點」的決策組合。但O(V3)的時間和O(V2)的空間，讓它只適用于稠密圖或節點數較少的場景。

選型決策可以總結為一張檢查表：

| 約束條件 | 算法 | 核心代價 | 關鍵限制 |

| 無權圖 | BFS | O(V+E) | 不認識權重 |

| 正權圖 | Dijkstra | O(E log V) | 負權邊致命 |

| 含負權邊 | Bellman-Ford | O(VE) | 可檢測負環 |

| 全點對 | Floyd-Warshall | O(V3) | 空間O(V2) |

但面試場景有個潛規則：能跑通的算法，比最優的算法更有價值。

回到開頭那個大廠面試。候選人的失誤不在于不會Dijkstra，而在于不知道有退路。Bellman-Ford的O(VE)在V=10?、E=10?的數據規模下確實會超時，但面試題的測試數據往往更溫和。

更現實的策略是：先寫Bellman-Ford保底，再討論優化到Dijkstra的可能性。這展示的是「在約束下做 trade-off」的產品思維，而非「背誦最優解」的學生思維。

某LeetCode周賽的賽后討論區，一條高贊評論寫道：「我用SPFA（Bellman-Ford的隊列優化版）水過了，正解是Dijkstra，但誰在乎呢？」

下次遇到圖論題，你會先檢查什么條件？