去年某大厂算法面，候选人卡在优先队列（一种按优先级取元素的数据结构）的实现上，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(V²)，二叉堆是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(V³ log V)或O(V²E)。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(V³)的时间和O(V²)的空间，让它只适用于稠密图或节点数较少的场景。
选型决策可以总结为一张检查表：
| 约束条件 | 算法 | 核心代价 | 关键限制 |
| 无权图 | BFS | O(V+E) | 不认识权重 |
| 正权图 | Dijkstra | O(E log V) | 负权边致命 |
| 含负权边 | Bellman-Ford | O(VE) | 可检测负环 |
| 全点对 | Floyd-Warshall | O(V³) | 空间O(V²) |
但面试场景有个潜规则：能跑通的算法，比最优的算法更有价值。
回到开头那个大厂面试。候选人的失误不在于不会Dijkstra，而在于不知道有退路。Bellman-Ford的O(VE)在V=10⁴、E=10⁵的数据规模下确实会超时，但面试题的测试数据往往更温和。
更现实的策略是：先写Bellman-Ford保底，再讨论优化到Dijkstra的可能性。这展示的是「在约束下做 trade-off」的产品思维，而非「背诵最优解」的学生思维。
某LeetCode周赛的赛后讨论区，一条高赞评论写道：「我用SPFA（Bellman-Ford的队列优化版）水过了，正解是Dijkstra，但谁在乎呢？」
下次遇到图论题，你会先检查什么条件？
热门跟贴