最短路径算法：Dijkstra算法、Bellman-Ford算法与Floyd-Warshall算法的比较与实现
字数 4376 2025-12-08 23:24:44

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

这是一个在面试中，特别是与图论、网络优化、路径规划相关岗位时，经常出现的核心问题。它考察你对不同最短路径算法核心思想、适用场景、复杂度以及权衡的深入理解。

题目描述

给定一个带权有向图（或无向图），以及一个源点（或需要求任意两点间最短距离）。图可能包含正权边，也可能包含负权边，但不包含负权回路（包含负权回路的最短路径无解）。请阐述如何计算从源点到所有其他顶点的最短路径（单源最短路径），或图中任意两顶点之间的最短路径（全源最短路径）。重点讲解Dijkstra、Bellman-Ford、Floyd-Warshall这三种经典算法的原理、步骤、复杂度、适用条件及实现要点。

解题过程与知识点讲解

我们首先明确“最短路径”的定义：在加权图中，从一个顶点到另一个顶点的路径上所有边的权值之和最小的那条路径。如果存在负权回路，则可以无限次绕行该回路使路径和趋近于负无穷，因此“最短”无意义。

第一步：算法分类与适用条件概览

  1. 单源最短路径 (Single-Source Shortest Paths, SSSP)：固定一个起点s，求s到图中所有其他顶点的最短距离和路径。
  2. 全源最短路径 (All-Pairs Shortest Paths, APSP)：求图中任意两个顶点之间的最短距离和路径。
算法 类型 边权要求 复杂度 核心思想
Dijkstra 单源 非负 (>=0) O((V+E)logV) (堆优化) 贪心 (Greedy) + 广度优先
Bellman-Ford 单源 任意 (可负)，但无负权回路 O(V*E) 动态规划 (DP) + 松弛 (Relaxation)
Floyd-Warshall 全源 任意 (可负)，但无负权回路 O(V^3) 动态规划 (DP) + 中间节点枚举

关键区别起点：边权的正负决定了你能使用哪种单源算法。Dijkstra算法不能处理带有负权边的图，因为其贪心策略（一旦确定最短距离的顶点不再更新）在负权边存在时会失效。

第二步：Dijkstra算法详解（贪心策略）

Dijkstra算法是解决非负权图单源最短路径问题的最有效算法。

核心思想：从源点s出发，逐步确定到各个顶点的最短距离。它维护一个“已确定最短路径的顶点集合”S。在每一步，从尚未确定的顶点中，选择一个当前距离s最近的顶点u加入S，然后利用u去“松弛”其邻居顶点v的距离。这个过程保证了每次加入S的顶点，其最短距离已经被最终确定。

核心操作——松弛 (Relaxation):
如果存在一条边u->v，权值为w，当前已知从s到u的最短距离为dist[u]，从s到v的当前距离为dist[v]。松弛操作检查：dist[u] + w < dist[v] 是否成立。如果成立，说明通过u再到v是一条更短的路径，于是更新dist[v] = dist[u] + w，并记录v的前驱节点为u。

算法步骤（使用优先队列/最小堆优化）：

  1. 初始化：dist[s] = 0，源点s的距离为0。其他所有顶点v的dist[v] = INF（无穷大）。将所有顶点(dist[v], v)加入最小堆（或优先队列）。S为空集。
  2. 循环，直到堆为空：
    a. 从堆中弹出当前dist最小的顶点u（即贪心选择）。如果dist[u]是过时的（即之前更新过，但旧值还在堆里），则跳过。
    b. 将u视为“已确定”（虽然没有显式集合S，但弹出即确定）。
    c. 遍历u的所有邻接边(u, v, w)：
    - 尝试松弛：new_dist = dist[u] + w。
    - 如果new_dist < dist[v]，则更新dist[v] = new_dist，并将(new_dist, v)压入堆中，并记录pre[v] = u。
  3. 结束：循环结束后，dist数组存储了从s到所有顶点的最短距离。通过pre数组可回溯得到路径。

复杂度分析：

  • 每个顶点入堆、出堆一次，操作复杂度O(logV)。
  • 每条边最多引发一次松弛操作，松弛可能伴随一次堆插入（O(logV)）。
  • 总复杂度：O((V+E)logV)。在稠密图（E≈V^2）中约为O(V^2 log V)，在稀疏图中效率很高。

为什么不能有负权边？
假设算法已确定顶点u的最短距离。如果存在负权边(v, u)，且v尚未确定，那么完全有可能通过v再到u（dist[v] + 负权值）得到一条比当前dist[u]更短的路径。但Dijkstra算法一旦从堆中弹出u，就再也不会用u作为目标点进行松弛，从而错过了这条更优路径。

第三步：Bellman-Ford算法详解（动态规划策略）

Bellman-Ford算法是解决可能含负权边的单源最短路径问题的通用算法，并能检测图中是否存在负权回路。

核心思想：动态规划。考虑从源点s到任意顶点v的最短路径，其边数不会超过V-1条（否则会包含环，而无负权回路时，正环/零环不会缩短路径，负权回路不允许存在）。算法进行V-1轮松弛操作，每轮松弛图中所有的边。经过V-1轮后，理论上所有最短路径都已被找出。如果再执行一轮（第V轮）松弛，还能有距离被更新，则说明图中存在从源点可达的负权回路。

算法步骤：

  1. 初始化：dist[s] = 0，其他dist[v] = INF。
  2. 进行V-1次迭代，每次迭代：
    • 遍历图中的所有边(u, v, w)。
    • 对每条边执行松弛操作：if dist[u] != INF && dist[u] + w < dist[v]: dist[v] = dist[u] + w。
  3. 检测负权回路（可选，但重要）：
    • 再进行一次（第V次）全边遍历和松弛。
    • 如果这次遍历中，还有任何dist[v]被更新，则说明图中存在从源点s可达的负权回路，算法报告错误。
  4. 结束：如果未检测到负权回路，则dist数组存储了从s到所有可达顶点的最短距离。

复杂度分析：

  • 需要进行V-1轮松弛，每轮遍历所有E条边。
  • 时间复杂度为O(V*E)。在稠密图（E≈V^2）中为O(V^3)，在稀疏图中为O(V^2)。

优点与缺点：

  • 优点：能处理负权边，并能检测负权回路。实现简单。
  • 缺点：时间复杂度高于Dijkstra，在无负权边的图中效率较低。

一个优化：如果在某一轮松弛中，没有任何dist值被更新，说明所有最短路径已确定，可以提前终止循环。这被称为SPFA算法的思想基础。

第四步：Floyd-Warshall算法详解（动态规划策略）

Floyd-Warshall算法是解决全源最短路径问题的经典算法，同样能处理负权边（无负权回路）。

核心思想：动态规划。定义dist[k][i][j]为：从顶点i到顶点j，且中间只允许经过顶点{1, 2, ..., k}的最短路径长度。

  • 初始状态 (k=0)：dist[0][i][j] 是边i->j的权值（无边则为INF，i=j为0）。
  • 状态转移：对于从i到j的路径，考虑是否经过顶点k：
    1. 不经过k：最短路径就是dist[k-1][i][j]。
    2. 经过k：最短路径是dist[k-1][i][k] + dist[k-1][k][j]。
      取两者最小值：dist[k][i][j] = min(dist[k-1][i][j], dist[k-1][i][k] + dist[k-1][k][j])。

由于状态dist[k][...]只依赖于dist[k-1][...]，因此可以用二维数组滚动更新，将空间复杂度优化到O(V^2)。

算法步骤（优化空间后）：

  1. 初始化：二维数组dist[i][j]。如果i==j，dist[i][j]=0；如果存在边i->j，dist[i][j]=w；否则dist[i][j]=INF。
  2. 三重循环： 
    for k in range(V):          # 枚举中间顶点k
    for i in range(V):      # 枚举起点i
        for j in range(V):  # 枚举终点j
            if dist[i][k] != INF and dist[k][j] != INF: # 防止溢出
                if dist[i][k] + dist[k][j] < dist[i][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]
  3. 结束：循环结束后，dist[i][j]即为顶点i到顶点j的最短距离。

复杂度分析：

  • 三重循环，时间复杂度为O(V^3)。
  • 空间复杂度为O(V^2)。

负权回路检测：算法结束后，检查dist[i][i]（即自己到自己的距离）。如果存在某个i使得dist[i][i] < 0，则说明图中存在经过顶点i的负权回路。

适用场景：适合求解稠密图的全源最短路径，或者图的顶点数V不大（几百以内）的情况。代码极其简洁。

总结对比

特性 Dijkstra Bellman-Ford Floyd-Warshall
问题类型 单源 单源 全源
边权限制 必须非负 可正可负，能检测负权回路 可正可负，能间接检测负权回路
核心策略 贪心 + 松弛 动态规划 (V-1轮松弛) 动态规划 (枚举中间点)
时间复杂度 O((V+E)logV) O(V*E) O(V^3)
空间复杂度 O(V+E) O(V) O(V^2)
最佳适用 非负权稀疏图，单源问题 含负权边的图，或需检测负环 稠密图的全源问题，或顶点数少

面试要点：

  1. 务必清晰指出Dijkstra不能处理负权边的原因。
  2. Bellman-Ford的V-1轮松弛的由来（最短路径最多V-1条边）。
  3. Floyd-Warshall的三重循环顺序（k, i, j）不能颠倒，因为这是动态规划的阶段。
  4. 能根据具体问题（单源/全源、有无负权、图稀疏/稠密）快速选择合适的算法。例如，地图导航（无负权，单源）用Dijkstra；金融网络中的套利检测（可能存在负权回路）用Bellman-Ford；需要预先计算所有点对距离的小规模图用Floyd-Warshall。
最短路径算法：Dijkstra算法、Bellman-Ford算法与Floyd-Warshall算法的比较与实现 这是一个在面试中，特别是与图论、网络优化、路径规划相关岗位时，经常出现的核心问题。它考察你对不同最短路径算法核心思想、适用场景、复杂度以及权衡的深入理解。 题目描述 给定一个 带权有向图 （或无向图），以及一个 源点 （或需要求任意两点间最短距离）。图可能包含 正权边 ，也可能包含 负权边 ，但不包含 负权回路 （包含负权回路的最短路径无解）。请阐述如何计算从源点到所有其他顶点的最短路径（单源最短路径），或图中任意两顶点之间的最短路径（全源最短路径）。重点讲解Dijkstra、Bellman-Ford、Floyd-Warshall这三种经典算法的原理、步骤、复杂度、适用条件及实现要点。 解题过程与知识点讲解 我们首先明确“最短路径”的定义：在加权图中，从一个顶点到另一个顶点的 路径上所有边的权值之和 最小的那条路径。如果存在负权回路，则可以无限次绕行该回路使路径和趋近于负无穷，因此“最短”无意义。 第一步：算法分类与适用条件概览 单源最短路径 (Single-Source Shortest Paths, SSSP) ：固定一个起点 s ，求 s 到图中所有其他顶点的最短距离和路径。 全源最短路径 (All-Pairs Shortest Paths, APSP) ：求图中 任意两个顶点 之间的最短距离和路径。 | 算法 | 类型 | 边权要求 | 复杂度 | 核心思想 | | :--- | :--- | :--- | :--- | :--- | | Dijkstra | 单源 | 非负 (>=0) | O((V+E)logV) (堆优化) | 贪心 (Greedy) + 广度优先 | | Bellman-Ford | 单源 | 任意 (可负)， 但无负权回路 | O(V* E) | 动态规划 (DP) + 松弛 (Relaxation) | | Floyd-Warshall | 全源 | 任意 (可负)， 但无负权回路 | O(V^3) | 动态规划 (DP) + 中间节点枚举 | 关键区别起点 ： 边权的正负 决定了你能使用哪种单源算法。Dijkstra算法 不能处理带有负权边的图 ，因为其贪心策略（一旦确定最短距离的顶点不再更新）在负权边存在时会失效。 第二步：Dijkstra算法详解（贪心策略） Dijkstra算法是解决 非负权图 单源最短路径问题的最有效算法。 核心思想 ：从源点 s 出发，逐步确定到各个顶点的最短距离。它维护一个“已确定最短路径的顶点集合” S 。在每一步，从尚未确定的顶点中，选择一个当前距离 s 最近 的顶点 u 加入 S ，然后利用 u 去“松弛”其邻居顶点 v 的距离。这个过程保证了每次加入 S 的顶点，其最短距离已经被最终确定。 核心操作——松弛 (Relaxation) : 如果存在一条边 u->v ，权值为 w ，当前已知从 s 到 u 的最短距离为 dist[u] ，从 s 到 v 的当前距离为 dist[v] 。松弛操作检查： dist[u] + w < dist[v] 是否成立。如果成立，说明通过 u 再到 v 是一条更短的路径，于是更新 dist[v] = dist[u] + w ，并记录 v 的前驱节点为 u 。 算法步骤（使用优先队列/最小堆优化） ： 初始化 ： dist[s] = 0 ，源点 s 的距离为0。其他所有顶点 v 的 dist[v] = INF （无穷大）。将所有顶点 (dist[v], v) 加入最小堆（或优先队列）。 S 为空集。 循环 ，直到堆为空： a. 从堆中弹出当前 dist 最小的顶点 u （即贪心选择）。如果 dist[u] 是过时的（即之前更新过，但旧值还在堆里），则跳过。 b. 将 u 视为“已确定”（虽然没有显式集合 S ，但弹出即确定）。 c. 遍历 u 的所有邻接边 (u, v, w) ： - 尝试松弛： new_dist = dist[u] + w 。 - 如果 new_dist < dist[v] ，则更新 dist[v] = new_dist ，并将 (new_dist, v) 压入堆中，并记录 pre[v] = u 。 结束 ：循环结束后， dist 数组存储了从 s 到所有顶点的最短距离。通过 pre 数组可回溯得到路径。 复杂度分析 ： 每个顶点入堆、出堆一次，操作复杂度O(logV)。 每条边最多引发一次松弛操作，松弛可能伴随一次堆插入（O(logV)）。 总复杂度： O((V+E)logV) 。在稠密图（E≈V^2）中约为O(V^2 log V)，在稀疏图中效率很高。 为什么不能有负权边？ 假设算法已确定顶点 u 的最短距离。如果存在负权边 (v, u) ，且 v 尚未确定，那么完全有可能通过 v 再到 u （ dist[v] + 负权值 ）得到一条比当前 dist[u] 更短的路径。但Dijkstra算法一旦从堆中弹出 u ，就再也不会用 u 作为目标点进行松弛，从而错过了这条更优路径。 第三步：Bellman-Ford算法详解（动态规划策略） Bellman-Ford算法是解决 可能含负权边 的单源最短路径问题的通用算法，并能 检测图中是否存在负权回路 。 核心思想 ：动态规划。考虑从源点 s 到任意顶点 v 的最短路径，其边数不会超过 V-1 条（否则会包含环，而无负权回路时，正环/零环不会缩短路径，负权回路不允许存在）。算法进行 V-1 轮松弛操作，每轮松弛图中所有的边。经过 V-1 轮后，理论上所有最短路径都已被找出。如果再执行一轮（第 V 轮）松弛，还能有距离被更新，则说明图中存在 从源点可达的负权回路 。 算法步骤 ： 初始化 ： dist[s] = 0 ，其他 dist[v] = INF 。 进行V-1次迭代 ，每次迭代： 遍历图中的 所有边 (u, v, w) 。 对每条边执行松弛操作： if dist[u] != INF && dist[u] + w < dist[v]: dist[v] = dist[u] + w 。 检测负权回路 （可选，但重要）： 再进行一次（第V次）全边遍历和松弛。 如果这次遍历中，还有任何 dist[v] 被更新，则说明图中存在从源点 s 可达的负权回路，算法报告错误。 结束 ：如果未检测到负权回路，则 dist 数组存储了从 s 到所有可达顶点的最短距离。 复杂度分析 ： 需要进行 V-1 轮松弛，每轮遍历所有 E 条边。 时间复杂度为 O(V* E) 。在稠密图（E≈V^2）中为O(V^3)，在稀疏图中为O(V^2)。 优点与缺点 ： 优点 ：能处理负权边，并能检测负权回路。实现简单。 缺点 ：时间复杂度高于Dijkstra，在无负权边的图中效率较低。 一个优化 ：如果在某一轮松弛中，没有任何 dist 值被更新，说明所有最短路径已确定，可以提前终止循环。这被称为 SPFA算法 的思想基础。 第四步：Floyd-Warshall算法详解（动态规划策略） Floyd-Warshall算法是解决 全源最短路径 问题的经典算法，同样能处理负权边（无负权回路）。 核心思想 ：动态规划。定义 dist[k][i][j] 为：从顶点 i 到顶点 j ，且中间只允许经过顶点 {1, 2, ..., k} 的最短路径长度。 初始状态 ( k=0 )： dist[0][i][j] 是边 i->j 的权值（无边则为INF， i=j 为0）。 状态转移 ：对于从 i 到 j 的路径，考虑是否经过顶点 k ： 不经过 k ：最短路径就是 dist[k-1][i][j] 。 经过 k ：最短路径是 dist[k-1][i][k] + dist[k-1][k][j] 。 取两者最小值： dist[k][i][j] = min(dist[k-1][i][j], dist[k-1][i][k] + dist[k-1][k][j]) 。 由于状态 dist[k][...] 只依赖于 dist[k-1][...] ，因此可以用二维数组滚动更新，将空间复杂度优化到O(V^2)。 算法步骤（优化空间后） ： 初始化 ：二维数组 dist[i][j] 。如果 i==j ， dist[i][j]=0 ；如果存在边 i->j ， dist[i][j]=w ；否则 dist[i][j]=INF 。 三重循环 ： 结束 ：循环结束后， dist[i][j] 即为顶点 i 到顶点 j 的最短距离。 复杂度分析 ： 三重循环，时间复杂度为 O(V^3) 。 空间复杂度为 O(V^2) 。 负权回路检测 ：算法结束后，检查 dist[i][i] （即自己到自己的距离）。如果存在某个 i 使得 dist[i][i] < 0 ，则说明图中存在经过顶点 i 的负权回路。 适用场景 ：适合求解稠密图的全源最短路径，或者图的顶点数V不大（几百以内）的情况。代码极其简洁。 总结对比 | 特性 | Dijkstra | Bellman-Ford | Floyd-Warshall | | :--- | :--- | :--- | :--- | | 问题类型 | 单源 | 单源 | 全源 | | 边权限制 | 必须非负 | 可正可负，能检测负权回路 | 可正可负，能间接检测负权回路 | | 核心策略 | 贪心 + 松弛 | 动态规划 (V-1轮松弛) | 动态规划 (枚举中间点) | | 时间复杂度 | O((V+E)logV) | O(V* E) | O(V^3) | | 空间复杂度 | O(V+E) | O(V) | O(V^2) | | 最佳适用 | 非负权稀疏图，单源问题 | 含负权边的图，或需检测负环 | 稠密图的全源问题，或顶点数少 | 面试要点 ： 务必清晰指出Dijkstra不能处理负权边的原因。 Bellman-Ford的 V-1 轮松弛的由来（最短路径最多V-1条边）。 Floyd-Warshall的三重循环顺序（ k, i, j ）不能颠倒，因为这是动态规划的阶段。 能根据具体问题（单源/全源、有无负权、图稀疏/稠密）快速选择合适的算法。例如，地图导航（无负权，单源）用Dijkstra；金融网络中的套利检测（可能存在负权回路）用Bellman-Ford；需要预先计算所有点对距离的小规模图用Floyd-Warshall。