去年某大廠算法面，候選人卡在優(yōu)先隊(duì)列（一種按優(yōu)先級(jí)取元素的數(shù)據(jù)結(jié)構(gòu)）的實(shí)現(xiàn)上，20分鐘沒(méi)調(diào)通。面試官換了個(gè)問(wèn)法：「Bellman-Ford會(huì)嗎？」候選人搖頭。面試結(jié)束。

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

最短路徑算法的選型，本質(zhì)是約束條件的翻譯游戲。LeetCode的圖論題不會(huì)告訴你該用哪個(gè)算法，它只給你一堆條件：有權(quán)還是無(wú)權(quán)？單源還是全點(diǎn)對(duì)？有沒(méi)有負(fù)權(quán)邊？

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

無(wú)權(quán)圖：BFS的領(lǐng)地

社交網(wǎng)絡(luò)的六度分隔、迷宮的最少步數(shù)、Word Ladder的單詞變換——這些場(chǎng)景的共同點(diǎn)是什么？每一步的代價(jià)恒定為1。

BFS（廣度優(yōu)先搜索）在這種場(chǎng)景下是統(tǒng)治級(jí)的。它的核心機(jī)制是層級(jí)擴(kuò)散：從起點(diǎn)出發(fā)，先訪問(wèn)所有距離為1的節(jié)點(diǎn)，再訪問(wèn)距離為2的，以此類推。第一次觸及某個(gè)節(jié)點(diǎn)時(shí)，走過(guò)的步數(shù)就是最短路徑。

很多題目會(huì)把圖藏起來(lái)。二維矩陣?yán)锩總€(gè)格子是節(jié)點(diǎn)，相鄰移動(dòng)是邊；Word Ladder里每個(gè)單詞是節(jié)點(diǎn)，單字符差異是邊。識(shí)別出這種隱式圖結(jié)構(gòu)，是解題的第一步。

但BFS有個(gè)硬邊界：它不認(rèn)識(shí)「權(quán)重」這個(gè)概念。一旦不同邊的代價(jià)不同，層級(jí)擴(kuò)散的邏輯就崩塌了——你無(wú)法再用「第幾層」來(lái)等價(jià)于「最短距離」。

正權(quán)圖：Dijkstra的貪心陷阱

當(dāng)?shù)缆酚虚L(zhǎng)短、航班有價(jià)格差異時(shí)，圖變成帶權(quán)圖。Dijkstra算法的直覺(jué)很樸素：總是先處理當(dāng)前距離起點(diǎn)最近的節(jié)點(diǎn)，并假設(shè)這個(gè)距離不會(huì)再被優(yōu)化。

這個(gè)假設(shè)成立的前提是：所有邊的權(quán)重為正。正權(quán)重保證了「繞路不可能更優(yōu)」——任何額外的邊只會(huì)增加總成本，不會(huì)讓已經(jīng)確定的最短路徑變得更短。

實(shí)現(xiàn)上，Dijkstra依賴優(yōu)先隊(duì)列來(lái)動(dòng)態(tài)獲取「當(dāng)前最小距離節(jié)點(diǎn)」。堆的插入和提取操作讓復(fù)雜度控制在O(E log V)，其中E是邊數(shù)，V是節(jié)點(diǎn)數(shù)。

但優(yōu)先隊(duì)列是面試中的高頻翻車點(diǎn)。數(shù)組實(shí)現(xiàn)是O(V2)，二叉堆是O(E log V)，斐波那契堆理論上更優(yōu)但沒(méi)人真的寫。很多候選人卡在堆的調(diào)整邏輯上，邊界條件一多就崩。

負(fù)權(quán)邊：Dijkstra的死刑，Bellman-Ford的入場(chǎng)券

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

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

第一輪迭代，找到所有只經(jīng)過(guò)1條邊的最短路徑；第二輪，找到最多經(jīng)過(guò)2條邊的最短路徑；以此類推。n個(gè)節(jié)點(diǎn)的圖，最短路徑最多包含n-1條邊，因此需要n-1輪迭代。

復(fù)雜度是O(VE)，比Dijkstra慢，但實(shí)現(xiàn)極簡(jiǎn)：兩個(gè)嵌套循環(huán)，外層V-1次，內(nèi)層遍歷所有邊。不需要堆，不需要復(fù)雜數(shù)據(jù)結(jié)構(gòu)。

更關(guān)鍵的是，Bellman-Ford能檢測(cè)負(fù)權(quán)環(huán)。如果第V輪迭代還能松弛成功，說(shuō)明存在可以無(wú)限降低成本的環(huán)路——這在金融套利檢測(cè)等場(chǎng)景中是核心需求。

全點(diǎn)對(duì)：Floyd-Warshall的空間換時(shí)間

當(dāng)問(wèn)題要求「任意兩點(diǎn)間的最短距離」時(shí)，單源算法需要執(zhí)行V次，總復(fù)雜度O(V3 log V)或O(V2E)。Floyd-Warshall用動(dòng)態(tài)規(guī)劃一次性解決：dp[k][i][j]表示「只允許經(jīng)過(guò)節(jié)點(diǎn)1到k作為中轉(zhuǎn)，i到j(luò)的最短距離」。

狀態(tài)轉(zhuǎn)移方程是經(jīng)典的：dp[k][i][j] = min(dp[k-1][i][j], dp[k-1][i][k] + dp[k-1][k][j])。空間可以滾動(dòng)優(yōu)化到二維，最終形式是三重循環(huán)。

這個(gè)算法的優(yōu)雅之處在于，它把「路徑」拆解為「是否經(jīng)過(guò)某個(gè)中轉(zhuǎn)點(diǎn)」的決策組合。但O(V3)的時(shí)間和O(V2)的空間，讓它只適用于稠密圖或節(jié)點(diǎn)數(shù)較少的場(chǎng)景。

選型決策可以總結(jié)為一張檢查表：

| 約束條件 | 算法 | 核心代價(jià) | 關(guān)鍵限制 |

| 無(wú)權(quán)圖 | BFS | O(V+E) | 不認(rèn)識(shí)權(quán)重 |

| 正權(quán)圖 | Dijkstra | O(E log V) | 負(fù)權(quán)邊致命 |

| 含負(fù)權(quán)邊 | Bellman-Ford | O(VE) | 可檢測(cè)負(fù)環(huán) |

| 全點(diǎn)對(duì) | Floyd-Warshall | O(V3) | 空間O(V2) |

但面試場(chǎng)景有個(gè)潛規(guī)則：能跑通的算法，比最優(yōu)的算法更有價(jià)值。

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

更現(xiàn)實(shí)的策略是：先寫B(tài)ellman-Ford保底，再討論優(yōu)化到Dijkstra的可能性。這展示的是「在約束下做 trade-off」的產(chǎn)品思維，而非「背誦最優(yōu)解」的學(xué)生思維。

某LeetCode周賽的賽后討論區(qū)，一條高贊評(píng)論寫道：「我用SPFA（Bellman-Ford的隊(duì)列優(yōu)化版）水過(guò)了，正解是Dijkstra，但誰(shuí)在乎呢？」

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