最短路径：Dijkstra、Bellman-Ford 与 Floyd
图算法学到这里，一个最自然、也最现实的问题就会出现：
从一个点到另一个点，怎么走代价最小？
这里的“代价”可以是很多东西：
- 距离最短；
- 时间最少；
- 花费最低；
- 风险最小；
- 路由跳数最少。
这就是最短路径问题。它之所以重要，是因为它几乎贯穿了所有网络、导航、调度和路径规划场景。但“最短路径”并不是只有一种算法，因为图的条件差别非常大：
- 权值是否都非负；
- 只求单源，还是求全源；
- 图规模大不大；
- 是否存在负权边。
也正因为此，Dijkstra、Bellman-Ford 和 Floyd 不是互相替代的关系，而是分别适用于不同条件的三类经典解法。
一、什么是最短路径问题
最短路径问题通常分成几类：
1. 单源最短路径
给定一个源点，求它到其他所有顶点的最短路径。
2. 单点对最短路径
只关心某个起点到某个终点的最短路。
3. 全源最短路径
要求任意两个顶点之间的最短路径。
不同算法的重点往往就体现在：
- 是求一源到多点；
- 还是求所有点对；
- 是不是允许负权边。
二、为什么最短路径不等于 BFS
前面说过，BFS 可以求无权图最短路，或者每条边权值都相同的情况。但一旦边权不同：
- “边数最少”不等于“总代价最小”；
- 少走一步未必更便宜；
- 这时就需要更一般的最短路径算法。
所以可以这样记：
- 无权图最短路，优先想 BFS；
- 带权图最短路，则要看权值性质选择算法。
三、Dijkstra 解决什么问题
Dijkstra 最经典的适用条件是：
求单源最短路径，且所有边权非负。
它的核心思想是贪心：
- 每次从尚未确定的顶点中，选出当前距离源点最近的那个；
- 一旦这个点被确定，它的最短距离就不会再被改写；
- 然后用它去尝试松弛相邻顶点。
这里“松弛”可以理解成：
- 看看通过当前点走过去，是否能让邻居的距离更短。
四、为什么 Dijkstra 要求边权非负
因为它的贪心成立依赖一个关键前提：
- 当前最小的暂定距离，以后不会再被负权边绕回来改小。
如果存在负权边，那么：
- 你今天看起来最短的路径；
- 明天可能通过一条负边被进一步缩短；
- 于是“先确定当前最小”这个贪心就失效了。
所以 Dijkstra 的适用边界一定要记牢：
有负权边时，不能直接用它。
五、Dijkstra 为什么常和优先队列一起出现
因为它需要反复做这样一件事：
- 从所有尚未处理的候选顶点中，快速找出当前距离最小的那个。
这和最小堆 / 优先队列的能力高度一致。于是高效实现通常是：
- 用优先队列维护候选点；
- 每次弹出当前最小距离顶点；
- 再做松弛更新。
所以前面学堆和优先队列，在最短路径这里再次成为核心工具。
六、什么是 Bellman-Ford
Bellman-Ford 也是单源最短路径算法，但它的适用范围更广：
它允许图中存在负权边，并且还能检测负权环。
它的核心思想不是贪心，而是动态地反复松弛所有边：
- 如果一条最短路径最多经过
k条边； - 那么不断用边去更新距离，最终就能传播出最优值。
更具体地说：
- 对所有边重复做松弛操作；
- 最多做
|V| - 1轮； - 因为一个简单路径最多经过
|V| - 1条边。
七、Bellman-Ford 为什么能处理负权边
因为它不依赖“当前最近点已经最终确定”这种贪心假设，而是更保守地不断传播距离更新。
它允许这样一种情况：
- 某个点今天还不是最优；
- 但过几轮之后，通过某条负边路径被改写得更短；
- 算法仍然能够接收并传播这个变化。
所以相比 Dijkstra，它更慢，但更通用。
八、Bellman-Ford 为什么能检测负权环
如果一张图存在从源点可达的负权环，那么：
- 你可以在这个环上绕很多圈；
- 总路径代价会越来越小；
- 最短路径就不再有意义。
Bellman-Ford 检测的方法通常是：
- 在做完
|V| - 1轮松弛后； - 再额外检查一轮；
- 如果还有边能继续被松弛；
- 就说明存在负权环。
这也是它非常重要的一个特点。
九、什么是 Floyd 算法
Floyd，通常指 Floyd-Warshall 算法，它解决的是：
全源最短路径问题，也就是任意两点之间的最短路径。
它的思路和前两者都不同，更像动态规划。
核心思想是：
- 逐步考虑“允许哪些中间点参与路径”；
- 假设当前允许经过前
k个点； - 那么
i到j的最短路，要么不经过k，要么经过k； - 于是就能写成状态转移。
这是一个非常经典的三重循环动态规划模型。
十、Floyd 为什么适合全源最短路径
因为它直接维护一个二维距离矩阵：
dist[i][j]表示i到j的当前最短距离；- 再通过逐步引入中转点不断更新。
最终结果就是所有点对之间的最短路径。
它的优点是：
- 思路统一；
- 代码相对简洁；
- 对负权边也能处理；
- 还能顺手做可达性闭包等变形。
但缺点也明显：
- 时间复杂度是
O(n^3)； - 空间复杂度通常是
O(n^2)； - 图特别大时不太适合。
十一、这三种算法该怎么选
可以先抓住最重要的决策点。
1. Dijkstra
适合：
- 单源最短路；
- 边权非负；
- 希望高效处理较大图。
2. Bellman-Ford
适合：
- 单源最短路；
- 图中可能有负权边；
- 还希望检测负权环。
3. Floyd
适合：
- 全源最短路；
- 图规模不算太大；
- 想一次性得到任意两点最短距离。
如果只记一句话，可以记成：
- 非负单源用 Dijkstra；
- 负权单源用 Bellman-Ford；
- 全点对用 Floyd。
十二、最短路径和最小生成树有什么区别
这两类问题很容易一起出现，但目标完全不同。
1. 最短路径
优化的是：
- 某个起点到终点的路径代价；
- 或所有点对之间的路径代价。
2. 最小生成树
优化的是：
- 把整张图连起来的总代价最小。
所以：
- 最短路径关注“走一条路最省”；
- 最小生成树关注“整体连网最省”。
不能混用。
十三、学习最短路径时最容易踩的坑
1. 有负权边还用 Dijkstra
这是最典型错误之一。
2. 把 BFS 当成所有最短路通解
BFS 只适合无权图或等权边。
3. 不区分单源和全源问题
这会直接影响算法选择。
4. 把最短路径和最小生成树混淆
二者优化目标完全不同。
总结
最短路径之所以重要，不只是因为它常见，而是因为它几乎是图优化问题里最基础的一类模型。真正值得先建立起来的，是这些核心认识：
- 最短路径问题要先分清：单源、单点对，还是全源；
- BFS 适合无权图，Dijkstra 适合非负权单源最短路；
- Bellman-Ford 适合有负权边并支持检测负权环；
- Floyd 适合规模较小图上的全源最短路；
- 选择算法的关键，不是死记名字，而是看权值条件、问题范围和图规模；
- 真正学会最短路径，不是会背三段代码，而是能先判断题目到底属于哪一类最短路模型。
把这一篇理解透之后，后面再去学关键路径和更复杂的图优化问题时，你会更清楚：不同算法虽然都在图上“算路径”，但它们背后优化的对象、前提和使用边界并不相同。
参考资源：