1. 简介
在本篇文章中，我们将深入探讨 Dijkstra 和 Floyd-Warshall 两种最短路径算法的核心差异。通过从算法范式、时间复杂度、适用场景等角度进行比较，帮助你更清晰地理解它们各自的特点和适用范围。
两种算法都广泛应用于图（Graph）结构中。图由一组节点（Vertices）和连接这些节点的边（Edges）组成。我们通常将每条边赋予一个非负整数的权重，表示两个节点之间的距离。一条路径的总长度是该路径上所有边权重的总和。最短路径问题的核心目标就是找出任意两个节点之间的最短路径：
如上图所示，节点集合为 $ V = {A, B, C} $，边集合为 $ E = {A-B, B-C, C-A} $，边上的数字表示权重。
我们先来分别回顾一下这两种算法各自解决的问题类型。
2. Dijkstra 算法
✅ 适用问题：单源最短路径（Single Source Shortest Path, SSSP）
Dijkstra 算法用于解决从一个起点出发，到图中所有其他节点的最短路径问题。它在诸如链路状态路由协议（Link-State Routing Protocol）中有广泛应用，每个节点通过 Dijkstra 算法计算出到其他节点的最短路径，从而构建网络拓扑视图。
⚠️ 注意：该算法不能处理负权边！
3. Floyd-Warshall 算法
✅ 适用问题：所有节点对之间的最短路径（All-Pairs Shortest Paths, APSP）
Floyd-Warshall 算法则更进一步，它用于计算图中任意两个节点之间的最短路径。相比 Dijkstra，它更适用于需要全局路径信息的场景，例如网络路由、交通规划等。
✅ 优点：支持负权边，但不能处理负权环。
⚠️ 缺点：计算开销较大，适合节点数量不大的图。
4. 算法对比
接下来我们从多个维度对 Dijkstra 和 Floyd-Warshall 进行对比。
4.1. 算法范式
Dijkstra 算法：采用贪心策略（Greedy），每一步都选择当前最优的局部路径，最终得到全局最优解。
- 适用于具有最优子结构和贪心选择性质的问题。
- 通常采用优先队列实现，执行方式是自顶向下。
Floyd-Warshall 算法：采用动态规划（Dynamic Programming, DP），通过逐步迭代更新路径信息。
- 适用于具有最优子结构和重叠子问题性质的问题。
- 通常采用二维数组实现，执行方式是自底向上。
4.2. 时间与空间复杂度
| 实现方式 | 时间复杂度 | 空间复杂度 |
|---|---|---|
| Dijkstra + 数组 | $ \mathcal{O}(V^2) $ | $ \mathcal{O}(V) $ |
| Dijkstra + 最小堆 | $ \mathcal{O}(E \log V) $ | $ \mathcal{O}(V) $ |
| Dijkstra + 斐波那契堆 | $ \mathcal{O}(E + V \log V) $ | $ \mathcal{O}(V) $ |
| Floyd-Warshall | $ \mathcal{O}(V^3) $ | $ \mathcal{O}(V^2) $ |
📌 说明：
- Dijkstra 的效率取决于实现方式。对于稀疏图（边数远小于节点数平方），使用堆优化更划算。
- Floyd-Warshall 虽然实现简单，但时间复杂度较高，适合节点数较少的图（如 $ V \leq 200 $）。
4.3. 适用限制
| 特性 | Dijkstra | Floyd-Warshall |
|---|---|---|
| 是否支持负权边 | ❌ 不支持 | ✅ 支持 |
| 是否支持负权环 | ❌ 不支持 | ❌ 不支持 |
| 是否能检测负权环 | ❌ | ✅ 可以检测 |
| 是否适合稀疏图 | ✅ 适合 | ❌ 不适合 |
| 是否适合稠密图 | ❌ 不适合 | ✅ 适合 |
📌 踩坑提醒：
- 如果图中存在负权边，使用 Dijkstra 可能会得到错误结果。
- Floyd-Warshall 虽然支持负权边，但如果图中存在负权环，会导致最短路径不存在（无限循环）。
5. 总结
| 维度 | Dijkstra | Floyd-Warshall |
|---|---|---|
| 解决问题 | 单源最短路径（SSSP） | 所有节点对最短路径（APSP） |
| 算法范式 | 贪心 | 动态规划 |
| 时间复杂度 | $ \mathcal{O}(V^2) $ 或更优 | $ \mathcal{O}(V^3) $ |
| 空间复杂度 | $ \mathcal{O}(V) $ | $ \mathcal{O}(V^2) $ |
| 支持负权边 | ❌ | ✅ |
| 检测负权环 | ❌ | ✅ |
| 实现难度 | 中等 | 简单 |
📌 使用建议：
- 如果只需要从一个起点出发找最短路径，优先使用 Dijkstra。
- 如果要找任意两个节点之间的最短路径，且图节点数不大，使用 Floyd-Warshall。
- 如果图中存在负权边但无负权环，考虑使用 Bellman-Ford 或其优化版本 SPFA。
两种算法各有千秋，选择时应结合具体问题和图的结构特征。希望这篇文章能帮助你更清楚地掌握它们的差异与适用场景。