xxx Floyd-Warshall 算法求解所有顶点对最短路径

字数 1588 2025-11-26 08:26:33

xxx Floyd-Warshall 算法求解所有顶点对最短路径

题目描述
给定一个带权有向图，其中可能包含负权边（但不允许存在负权环），要求计算图中任意两个顶点之间的最短路径距离。该问题称为所有顶点对最短路径问题（All-Pairs Shortest Paths, APSP）。Floyd-Warshall 算法通过动态规划高效解决此问题，其时间复杂度为 O(V³)，适用于顶点数不超过几百的稠密图。

解题过程

问题分析与关键思路
- 目标：计算任意两个顶点 i 和 j 之间的最短路径距离。
- 核心思想：动态规划。定义状态 dist[k][i][j] 表示“从顶点 i 到 j，且中间顶点编号不超过 k 的所有路径中的最小距离”。通过逐步允许更多顶点作为中间顶点来更新最短路径。
- 优化：使用二维数组进行空间压缩，直接在原矩阵上更新。
算法步骤详解
- 步骤 1：初始化距离矩阵
  创建一个二维数组 dist，大小为 V×V（V 为顶点数）：
  - 若 i = j，则 dist[i][j] = 0（顶点到自身的距离为 0）。
  - 若存在边 (i, j)，则 dist[i][j] 为边权。
  - 否则，dist[i][j] = ∞（表示暂不可达）。
```
# 示例：图的邻接矩阵表示
dist = [[0, 3, ∞, 5],
       [2, 0, ∞, 4],
       [∞, 1, 0, ∞],
       [∞, ∞, 2, 0]]
```
- 步骤 2：三重循环动态更新
  依次允许每个顶点 k（0 到 V-1）作为中间顶点，更新所有顶点对 (i, j) 的距离：
```
对于 k 从 0 到 V-1：
    对于 i 从 0 到 V-1：
        对于 j 从 0 到 V-1：
            若 dist[i][k] + dist[k][j] < dist[i][j]：
                更新 dist[i][j] = dist[i][k] + dist[k][j]
```
  更新逻辑：
  - 当允许顶点 k 作为中间顶点时，路径 i → j 可能通过 k 缩短，即比较“当前路径 i→j”与“新路径 i→k→j”的长度。
  - 注意：即使 dist[i][k] 或 dist[k][j] 为 ∞，加法结果仍为 ∞，不会影响正确性。
- 步骤 3：检测负权环
  算法结束后，检查主对角线元素：
  - 若存在 dist[i][i] < 0，说明图中存在负权环（因为绕环一周可无限缩短距离）。
  - 若无负权环，dist[i][j] 即为 i 到 j 的最短距离。
示例演示
考虑包含 4 个顶点的图（顶点编号 0~3），初始距离矩阵如下：
```
dist = [
  [0, 3, ∞, 5],
  [2, 0, ∞, 4],
  [∞, 1, 0, ∞],
  [∞, ∞, 2, 0]
]
```
- k=0：允许顶点 0 作为中间顶点。
  - 更新 dist[2][1]：原为 ∞，现通过 0→2→0→1？不可行（仍 ∞）。
  - 更新 dist[1][3]：原为 4，但 1→0→3 距离为 2+5=7，无需更新。
    矩阵无变化。
- k=1：允许顶点 1 作为中间顶点。
  - 更新 dist[0][3]：原为 5，但 0→1→3 距离为 3+4=7，无需更新。
  - 更新 dist[2][0]：原为 ∞，但 2→1→0 距离为 1+2=3，更新为 3。
  - 更新 dist[2][3]：原为 ∞，但 2→1→3 距离为 1+4=5，更新为 5。
- k=2：允许顶点 2 作为中间顶点。
  - 更新 dist[1][0]：原为 2，但 1→2→0 距离为 ∞+3？不可行。
  - 更新 dist[3][1]：原为 ∞，但 3→2→1 距离为 2+1=3，更新为 3。
  - 更新 dist[3][0]：原为 ∞，但 3→2→0 距离为 2+3=5，更新为 5。
- k=3：允许顶点 3 作为中间顶点。
  - 更新 dist[0][2]：原为 ∞，但 0→3→2 距离为 5+2=7，更新为 7。
  - 更新 dist[1][2]：原为 ∞，但 1→3→2 距离为 4+2=6，更新为 6。
    最终矩阵：
```
[0, 3, 7, 5]
[2, 0, 6, 4]
[3, 1, 0, 5]
[5, 3, 2, 0]
```
算法特性与注意事项
- 时间复杂度：O(V³)，因三重循环。
- 空间复杂度：O(V²)，仅存储距离矩阵。
- 适用场景：稠密图且顶点数较少时；可处理负权边，但不能有负权环。
- 扩展功能：通过记录前驱矩阵可重构具体路径。

通过以上步骤，Floyd-Warshall 算法系统地计算出所有顶点对之间的最短路径，其动态规划思想确保了全局最优解。

xxx Floyd-Warshall 算法求解所有顶点对最短路径题目描述给定一个带权有向图，其中可能包含负权边（但不允许存在负权环），要求计算图中任意两个顶点之间的最短路径距离。该问题称为所有顶点对最短路径问题（All-Pairs Shortest Paths, APSP）。Floyd-Warshall 算法通过动态规划高效解决此问题，其时间复杂度为 O(V³)，适用于顶点数不超过几百的稠密图。解题过程问题分析与关键思路目标：计算任意两个顶点 i 和 j 之间的最短路径距离。核心思想：动态规划。定义状态 dist[k][i][j] 表示“从顶点 i 到 j，且中间顶点编号不超过 k 的所有路径中的最小距离”。通过逐步允许更多顶点作为中间顶点来更新最短路径。优化：使用二维数组进行空间压缩，直接在原矩阵上更新。算法步骤详解步骤 1：初始化距离矩阵创建一个二维数组 dist ，大小为 V×V（V 为顶点数）：若 i = j，则 dist[i][j] = 0 （顶点到自身的距离为 0）。若存在边 (i, j)，则 dist[i][j] 为边权。否则， dist[i][j] = ∞ （表示暂不可达）。步骤 2：三重循环动态更新依次允许每个顶点 k（0 到 V-1）作为中间顶点，更新所有顶点对 (i, j) 的距离：更新逻辑：当允许顶点 k 作为中间顶点时，路径 i → j 可能通过 k 缩短，即比较“当前路径 i→j”与“新路径 i→k→j”的长度。注意：即使 dist[ i][ k] 或 dist[ k][ j ] 为 ∞，加法结果仍为 ∞，不会影响正确性。步骤 3：检测负权环算法结束后，检查主对角线元素：若存在 dist[i][i] < 0 ，说明图中存在负权环（因为绕环一周可无限缩短距离）。若无负权环， dist[i][j] 即为 i 到 j 的最短距离。示例演示考虑包含 4 个顶点的图（顶点编号 0~3），初始距离矩阵如下： k=0 ：允许顶点 0 作为中间顶点。更新 dist[ 2][ 1 ]：原为 ∞，现通过 0→2→0→1？不可行（仍 ∞）。更新 dist[ 1][ 3 ]：原为 4，但 1→0→3 距离为 2+5=7，无需更新。矩阵无变化。 k=1 ：允许顶点 1 作为中间顶点。更新 dist[ 0][ 3 ]：原为 5，但 0→1→3 距离为 3+4=7，无需更新。更新 dist[ 2][ 0 ]：原为 ∞，但 2→1→0 距离为 1+2=3，更新为 3。更新 dist[ 2][ 3 ]：原为 ∞，但 2→1→3 距离为 1+4=5，更新为 5。 k=2 ：允许顶点 2 作为中间顶点。更新 dist[ 1][ 0 ]：原为 2，但 1→2→0 距离为 ∞+3？不可行。更新 dist[ 3][ 1 ]：原为 ∞，但 3→2→1 距离为 2+1=3，更新为 3。更新 dist[ 3][ 0 ]：原为 ∞，但 3→2→0 距离为 2+3=5，更新为 5。 k=3 ：允许顶点 3 作为中间顶点。更新 dist[ 0][ 2 ]：原为 ∞，但 0→3→2 距离为 5+2=7，更新为 7。更新 dist[ 1][ 2 ]：原为 ∞，但 1→3→2 距离为 4+2=6，更新为 6。最终矩阵：算法特性与注意事项时间复杂度：O(V³)，因三重循环。空间复杂度：O(V²)，仅存储距离矩阵。适用场景：稠密图且顶点数较少时；可处理负权边，但不能有负权环。扩展功能：通过记录前驱矩阵可重构具体路径。通过以上步骤，Floyd-Warshall 算法系统地计算出所有顶点对之间的最短路径，其动态规划思想确保了全局最优解。