Floyd-Warshall 算法概念
Floyd-Warshall 算法定义
Floyd-Warshall 算法是一种经典的 **动态规划** 算法，用于解决 **全源最短路径 (All-Pairs Shortest Paths)** 问题。它能找出在一个加权有向图（或无向图）中，所有顶点对之间的最短路径长度。
算法核心思想：对于任意一对顶点 (i, j)，它们之间的最短路径要么是直接相连的边，要么是经过某个（或某些）中间顶点 k 的路径。算法通过迭代地考虑每个顶点作为中间顶点，来逐步优化所有顶点对之间的最短距离。
关键点提示： 理解动态规划的状态转移。`dp[k][i][j]` 表示“只允许使用编号 1 到 k 的顶点作为中间点时，从 i 到 j 的最短路径长度”。Floyd-Warshall 通过巧妙的空间优化，将 `k` 这一维省略，状态转移方程简化为 `dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])`。
应用场景
Floyd-Warshall 算法虽然时间复杂度较高 (O(n³))，但在某些场景下非常有用，特别是当需要知道图中 **任意两点** 间的最短距离时：
- 交通网络： 计算任意两个城市或地点之间的最短行车距离或时间。
- 网络路由： 在小型网络中计算路由表，确定数据包传输的最优路径。
- 社交网络分析： 计算两个人之间的“最短关系链”（例如，六度分隔理论）。
- 生物信息学： 分析分子结构或基因序列之间的关系。
- 传递闭包： 判断图中任意两点是否可达（将边权视为1，若最短路有限则可达）。
关键点提示： 与 Dijkstra 或 Bellman-Ford 等单源最短路算法不同，Floyd-Warshall 一次性计算所有顶点对。如果图是稠密的，或者需要频繁查询任意两点间距离，它可能比多次运行单源算法更高效。它还可以处理带负权边的图（只要图中不存在负权环）。
算法思路概览
Floyd-Warshall 算法的实现非常简洁，主要依赖一个三层嵌套循环：
1. 初始化： 创建一个距离矩阵 `dist[][]`，`dist[i][j]` 初始化为顶点 i 到 j 的直接边权重（若无直连边则为无穷大 ∞，`dist[i][i]` 为 0）。
2. 迭代更新 (核心)：
- 外层循环 `k` 从 0 到 n-1 (n 为顶点数)：表示当前允许经过的 **中间顶点** 的最大编号。
- 中层循环 `i` 从 0 到 n-1：表示路径的 **起点**。
- 内层循环 `j` 从 0 到 n-1：表示路径的 **终点**。
3. 状态转移： 在循环内部，检查是否可以通过中间顶点 `k` 缩短 `i` 到 `j` 的距离：
`if (dist[i][k] + dist[k][j] < dist[i][j])`
如果是，则更新 `dist[i][j] = dist[i][k] + dist[k][j]`。
4. 结束： 当所有 `k` 都遍历完毕后，`dist[][]` 矩阵就包含了所有顶点对之间的最短路径长度。
关键点提示： 理解循环的顺序至关重要！`k` 必须是 **最外层** 循环。这保证了在计算 `dist[i][j]` 时，`dist[i][k]` 和 `dist[k][j]` 的值已经是基于只允许使用 {0, 1, ..., k-1} 作为中间节点得到的最短路径。时间复杂度 O(n³)，空间复杂度 O(n²)。
Floyd-Warshall 算法演示
请生成图或选择示例开始演示
控制面板
允许
动画控制
点击 "生成随机图" 或 "加载示例图" 来初始化。然后使用控制按钮开始或单步执行算法。
图结构可视化
Floyd-Warshall 算法 C++ 核心实现
// V 是顶点数量, INF 是无穷大
void floydWarshall(vector<vector<int>>& dist) {
int V = dist.size();
// k 是中间顶点
for (int k = 0; k < V; k++) {
// i 是起始顶点
for (int i = 0; i < V; i++) {
// j 是结束顶点
for (int j = 0; j < V; j++) {
// 如果 dist[i][k] 或 dist[k][j] 是无穷大, 跳过
if (dist[i][k] != INF && dist[k][j] != INF) {
// 松弛操作: 尝试通过 k 更新 i 到 j 的距离
if (dist[i][k] + dist[k][j] < dist[i][j]) {
dist[i][j] = dist[i][k] + dist[k][j];
}
}
}
}
}
}
距离矩阵 (初始状态 D-1)
| ↓ S \\ T → |
|---|