最短路径算法：Dijkstra算法、Bellman-Ford算法与Floyd-Warshall算法的比较与实现
字数 2980 2025-12-09 07:47:36

最短路径算法：Dijkstra算法、Bellman-Ford算法与Floyd-Warshall算法的比较与实现

这是一个图论中的核心面试考点，涉及三种经典的求解最短路径的算法。它们的原理、适用场景和实现方式各不相同，理解它们的区别是解决相关问题的关键。

我将为你详细拆解这三个算法，从问题描述到逐步推导，最后进行比较。

1. 问题描述

给定一个带权图，我们希望找到从图中某个顶点（源点）到其他所有顶点，或者图中任意两顶点之间的最短路径长度。这里的“最短”指的是路径上所有边的权重之和最小。

根据图的特征，算法选择不同：

  • 边权： 可以是正数、负数或零。
  • 图类型： 有向图或无向图。
  • 需求： 单源（一个起点）还是全源（所有点对）。

2. Dijkstra算法（单源，非负权）

Dijkstra算法用于求解边权非负的图中，单一起点到其他所有点的最短路径。

核心思想：贪心策略。维护一个“已确定最短距离”的顶点集合S，每次从“未确定”的集合中，选取一个距离起点最近的顶点加入S，并利用它来“松弛”（更新）其邻居顶点的距离。

逐步讲解（以节点0为起点）：

步骤1：初始化

  • 创建一个距离数组dist[]，dist[0] = 0，其他设为无穷大（∞）。
  • 创建一个集合visited（或使用优先队列），标记节点是否已确定最短距离。初始时都未确定。

步骤2：主循环

  1. 从所有未确定的节点中，选出当前dist值最小的节点u。（这个dist[u]就是它到起点的最终最短距离，为什么？因为是所有未确定点中距离最小的，且边权非负，不可能通过其他路径变得更小。）
  2. 将节点u标记为“已确定”。
  3. 松弛操作： 遍历u的所有邻居节点v。如果 dist[u] + weight(u, v) < dist[v]，则更新 dist[v] = dist[u] + weight(u, v)。这表示“经过u到v”是一条更短的路径。

步骤3：重复
重复步骤2，直到所有节点都被确定，或所有未确定节点的dist都为∞（表示不可达）。

时间复杂度：

  • 使用邻接矩阵和简单遍历找最小节点：O(V²)。
  • 使用最小堆（优先队列） 优化：O((V+E) log V)，适合稀疏图。

关键限制：边权不能为负。如果存在负权边，可能在后面找到一条“绕远”但包含负权边的路径，使得之前已“确定”的节点距离能被更新，破坏了贪心选择的基础。

3. Bellman-Ford算法（单源，可处理负权，检测负环）

该算法用于求解有向图（无向图需拆成两条有向边）中，单一起点到其他所有点的最短路径。它可以处理边权为任意实数的情况，并能检测图中是否存在从源点可达的负权环。

核心思想：动态规划/松弛。对图中的所有边进行V-1轮松弛操作。因为最短路径最多包含V-1条边。

逐步讲解：

步骤1：初始化
与Dijkstra相同，dist[源点] = 0，其他为∞。

步骤2：进行V-1轮松弛

  • 在每一轮中，遍历图中的所有边(u, v, w)。
  • 对每一条边，执行松弛操作：如果 dist[u] + w < dist[v]，则更新 dist[v] = dist[u] + w。

为什么是V-1轮？
在一个没有负权环的图中，任意两点间的最短路径最多经过V-1条边。经过V-1轮对所有边的松弛，足以让最短路径信息从源点“传递”到所有可达的节点。

步骤3：检测负权环（可选但重要）
再进行第V轮松弛。如果在这一轮中，还有任何dist值能被更新，则说明图中存在从源点可达的负权环。因为如果没有负环，V-1轮后所有dist应已收敛。

时间复杂度：O(V * E)，因为进行了V-1轮，每轮遍历所有E条边。

关键点：能处理负权，能检测负环，但比Dijkstra慢。

4. Floyd-Warshall算法（全源）

该算法用于求解任意两个顶点之间的最短路径。

核心思想：动态规划。定义dp[k][i][j]为：从i到j，且只允许使用前k个顶点（编号1...k）作为中间节点的最短路径长度。通过状态转移，最终得到任意两点间的最短路径。

空间优化后的逐步讲解：
我们通常使用二维数组dist[i][j]直接保存当前计算出的i到j的最短距离。

步骤1：初始化

  • 如果i==j，dist[i][j] = 0。
  • 如果存在边i->j，dist[i][j] = weight(i, j)。
  • 否则，dist[i][j] = ∞。

步骤2：三重循环动态规划
核心代码极其简洁：
for (k from 0 to V-1)
for (i from 0 to V-1)
for (j from 0 to V-1)
if (dist[i][k] + dist[k][j] < dist[i][j])
dist[i][j] = dist[i][k] + dist[k][j];

如何理解？

  • 最外层的k，代表我们“允许”使用的中间节点的范围。
  • 对于固定的k，dist[i][j]的更新意味着：看看“从i到k”加上“从k到j”的路径，是否比当前已知的“i到j”的路径更短。也就是尝试用节点k来缩短i到j的距离。

步骤3：结果
当三层循环结束时，dist[i][j]中存储的就是节点i到节点j的最终最短路径长度。

时间复杂度：O(V³)，因为三重循环。
空间复杂度：O(V²)。

关键点：代码简单，能求出所有点对的距离。也能处理负权边（但不能有负权环，否则最短路径无定义，距离会趋近于-∞）。

5. 三种算法的核心比较

特性 Dijkstra算法 Bellman-Ford算法 Floyd-Warshall算法
解决问题 单源最短路径 单源最短路径 全源最短路径
图类型 有向图、无向图 主要是有向图 有向图、无向图
边权要求 必须非负 可为任意值（正、负、零） 可为任意值（但不能有负权环）
核心能力 贪心，效率高 能检测从源点可达的负权环 代码简单，直接求出所有点对距离
经典时间复杂度 O((V+E) log V) O(V*E) O(V³)
适用场景 路由算法、地图导航（权值为正） 包含负权变的场景，如金融套利检测 需要计算任意两点距离，且图规模不大时

总结一下记忆要点：

  1. 只问一个起点到其他点，且边权非负 -> 首选Dijkstra（用堆优化）。
  2. 一个起点到其他点，但边权有负，或者要检测负环 -> 用Bellman-Ford。
  3. 要问任意两点之间的距离 -> 用Floyd-Warshall。

理解这三种算法的差异、内在原理和实现细节，是应对大厂图论相关面试题的坚实基础。

最短路径算法：Dijkstra算法、Bellman-Ford算法与Floyd-Warshall算法的比较与实现 这是一个图论中的核心面试考点，涉及三种经典的求解最短路径的算法。它们的原理、适用场景和实现方式各不相同，理解它们的区别是解决相关问题的关键。 我将为你详细拆解这三个算法，从问题描述到逐步推导，最后进行比较。 1. 问题描述 给定一个 带权图 ，我们希望找到从图中某个顶点（源点）到其他所有顶点，或者图中任意两顶点之间的 最短路径 长度。这里的“最短”指的是路径上所有边的 权重之和最小 。 根据图的特征，算法选择不同： 边权 ： 可以是正数、负数或零。 图类型 ： 有向图或无向图。 需求 ： 单源（一个起点）还是全源（所有点对）。 2. Dijkstra算法（单源，非负权） Dijkstra算法用于求解 边权非负 的图中， 单一起点 到其他所有点的最短路径。 核心思想 ：贪心策略。维护一个“已确定最短距离”的顶点集合S，每次从“未确定”的集合中，选取一个距离起点 最近 的顶点加入S，并利用它来“松弛”（更新）其邻居顶点的距离。 逐步讲解 （以节点0为起点）： 步骤1：初始化 创建一个距离数组 dist[] ， dist[0] = 0 ，其他设为无穷大（∞）。 创建一个集合 visited （或使用优先队列），标记节点是否已确定最短距离。初始时都未确定。 步骤2：主循环 从所有 未确定 的节点中，选出当前 dist 值最小的节点 u 。（这个 dist[u] 就是它到起点的最终最短距离，为什么？因为是所有未确定点中距离最小的，且边权非负，不可能通过其他路径变得更小。） 将节点 u 标记为“已确定”。 松弛操作 ： 遍历 u 的所有邻居节点 v 。如果 dist[u] + weight(u, v) < dist[v] ，则更新 dist[v] = dist[u] + weight(u, v) 。这表示“经过 u 到 v ”是一条更短的路径。 步骤3：重复 重复步骤2，直到所有节点都被确定，或所有未确定节点的 dist 都为∞（表示不可达）。 时间复杂度 ： 使用邻接矩阵和简单遍历找最小节点：O(V²)。 使用 最小堆（优先队列） 优化：O((V+E) log V)，适合稀疏图。 关键限制 ： 边权不能为负 。如果存在负权边，可能在后面找到一条“绕远”但包含负权边的路径，使得之前已“确定”的节点距离能被更新，破坏了贪心选择的基础。 3. Bellman-Ford算法（单源，可处理负权，检测负环） 该算法用于求解 有向图 （无向图需拆成两条有向边）中，单一起点到其他所有点的最短路径。它可以处理 边权为任意实数 的情况，并能 检测图中是否存在从源点可达的负权环 。 核心思想 ：动态规划/松弛。对图中的所有边进行 V-1 轮松弛操作。因为最短路径最多包含 V-1 条边。 逐步讲解 ： 步骤1：初始化 与Dijkstra相同， dist[源点] = 0 ，其他为∞。 步骤2：进行V-1轮松弛 在每一轮中， 遍历图中的所有边 (u, v, w) 。 对每一条边，执行松弛操作：如果 dist[u] + w < dist[v] ，则更新 dist[v] = dist[u] + w 。 为什么是V-1轮？ 在一个没有负权环的图中，任意两点间的最短路径最多经过 V-1 条边。经过 V-1 轮对所有边的松弛，足以让最短路径信息从源点“传递”到所有可达的节点。 步骤3：检测负权环（可选但重要） 再进行 第V轮 松弛。如果在这一轮中，还有任何 dist 值能被更新，则说明图中存在 从源点可达的负权环 。因为如果没有负环， V-1 轮后所有 dist 应已收敛。 时间复杂度 ：O(V * E)，因为进行了V-1轮，每轮遍历所有E条边。 关键点 ：能处理负权，能检测负环，但比Dijkstra慢。 4. Floyd-Warshall算法（全源） 该算法用于求解 任意两个顶点 之间的最短路径。 核心思想 ：动态规划。定义 dp[k][i][j] 为：从 i 到 j ，且 只允许使用前k个顶点（编号1...k）作为中间节点 的最短路径长度。通过状态转移，最终得到任意两点间的最短路径。 空间优化后的逐步讲解 ： 我们通常使用二维数组 dist[i][j] 直接保存当前计算出的i到j的最短距离。 步骤1：初始化 如果 i==j ， dist[i][j] = 0 。 如果存在边 i->j ， dist[i][j] = weight(i, j) 。 否则， dist[i][j] = ∞ 。 步骤2：三重循环动态规划 核心代码极其简洁： for (k from 0 to V-1) for (i from 0 to V-1) for (j from 0 to V-1) if (dist[i][k] + dist[k][j] < dist[i][j]) dist[i][j] = dist[i][k] + dist[k][j]; 如何理解？ 最外层的 k ，代表我们“允许”使用的中间节点的范围。 对于固定的 k ， dist[i][j] 的更新意味着：看看“从i到k”加上“从k到j”的路径，是否比当前已知的“i到j”的路径更短。也就是 尝试用节点k来缩短i到j的距离 。 步骤3：结果 当三层循环结束时， dist[i][j] 中存储的就是节点 i 到节点 j 的最终最短路径长度。 时间复杂度 ：O(V³)，因为三重循环。 空间复杂度 ：O(V²)。 关键点 ：代码简单，能求出所有点对的距离。也能处理负权边（但不能有负权环，否则最短路径无定义，距离会趋近于-∞）。 5. 三种算法的核心比较 | 特性 | Dijkstra算法 | Bellman-Ford算法 | Floyd-Warshall算法 | | :--- | :--- | :--- | :--- | | 解决问题 | 单源最短路径 | 单源最短路径 | 全源 最短路径 | | 图类型 | 有向图、无向图 | 主要是有向图 | 有向图、无向图 | | 边权要求 | 必须非负 | 可为任意值（正、负、零） | 可为任意值（但不能有负权环） | | 核心能力 | 贪心，效率高 | 能检测从源点可达的负权环 | 代码简单，直接求出所有点对距离 | | 经典时间复杂度 | O((V+E) log V) | O(V* E) | O(V³) | | 适用场景 | 路由算法、地图导航（权值为正） | 包含负权变的场景，如金融套利检测 | 需要计算任意两点距离，且图规模不大时 | 总结一下记忆要点 ： 只问一个起点到其他点，且边权非负 -> 首选 Dijkstra （用堆优化）。 一个起点到其他点，但边权有负，或者要检测负环 -> 用 Bellman-Ford 。 要问任意两点之间的距离 -> 用 Floyd-Warshall 。 理解这三种算法的差异、内在原理和实现细节，是应对大厂图论相关面试题的坚实基础。