多源最短路径:Floyd 算法
原创约 3128 字
本文讲解的例题
LeetCode | 力扣 | 难度 |
---|---|---|
1334. Find the City With the Smallest Number of Neighbors at a Threshold Distance | 1334. 阈值距离内邻居最少的城市 | 🟠 |
在 图结构最短路径算法概览 中,我们详细介绍了图论中单源最短路径、多源最短路径、点对点最短路径几种场景,以及几种经典最短路径算法的区别与联系。
在 最便宜的旅行路径 中,我们用动态规划求解过从 src
到 dst
的最短路径(点对点最短路径问题),而本文要解决的是多源最短路径问题,不能直接套用。
Floyd 算法基于动态规划思想,代码实现非常简单,但想要彻底理解其原理,需要费点功夫。下面先直接给出 Floyd 算法的代码以及例题,然后再详细讲解状态转移方程的推导过程。
Floyd 算法代码
Floyd 算法的代码如下,其中 Graph
是 图结构代码实现 中的通用接口:
int[][] floyd(Graph graph) {
int n = graph.nodeCount();
// 定义:dp[i][j] 的值为节点 i 到节点 j 的最短路径权重
int[][] dp = new int[n][n];
// base case
// 节点到其自身的路径权重为 0,所以 dp[i][i] 初始化为 0
// 对于直接相邻的节点,dp[i][j] 初始化为边的权重
// 对于不直接相邻的节点,dp[i][j] 初始化为 +inf
for (int i = 0; i < n; i++) {
Arrays.fill(dp[i], Integer.MAX_VALUE);
}
for (int i = 0; i < n; i++) {
dp[i][i] = 0;
}
for (int i = 0; i < n; i++) {
for (Edge edge : graph.neighbors(i)) {
int j = edge.to;
int weight = edge.weight;
dp[i][j] = weight;
}
}
// 状态转移
for (int k = 0; k < n; k++) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
// 为了防止 dp[i][k] + dp[k][j] 导致 int 溢出,需要额外判断
if (dp[i][k] != Integer.MAX_VALUE && dp[k][j] != Integer.MAX_VALUE) {
dp[i][j] = Math.min(dp[i][j], dp[i][k] + dp[k][j]);
}
}
}
}
return dp;
}
// 计算多源最短路径
// 其中 dist[i][j] 为节点 i 到节点 j 的最短路径权重
int[][] dist = floyd(graph);
可以看出上述代码就是一个标准的动态规划问题的解法代码,其中:
dp
数组的定义是 dp[i][j]
存储节点 i
到节点 j
的最短路径权重。
对于直接相邻的节点 i, j
,dp[i][j]
的值初始化为边的权重,不直接相邻的节点,初始化为 +inf
,这就是 base case。
状态转移方程就是三层嵌套 for 循环的部分,也是 Floyd 算法的核心:
// 状态转移
for (int k = 0; k < n; k++) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
dp[i][j] = Math.min(dp[i][j], dp[i][k] + dp[k][j]);
}
}
}
这样,Floyd 算法就完成了,时间复杂度是 ,空间复杂度是 ,其中 是图的节点数。