算法图算法

Floyd算法

字数统计: 1.6k字   |   阅读时长: 6分
, , ,

摘要: Floyd算法的原理与代码模板

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

Floyd(1936-2001)

历届图灵奖得主基本上都有高学历、高学位，绝大多数有博士头衔。这是可以理解的，因为创新型人才需要有很好的文化素养，丰富的知识底蕴，因而必须接受良好的教育，但事情总有例外。

1978 年图灵奖获得者、斯坦福大学计算机科学系教授，前后断言法的创始人，堆排序算法和Floyd-Warshall算法的创始人之一，罗伯特·弗洛伊德就是一位“自学成才的计算机科学家”。

本文我们以力扣 1334 为模板题，串讲一下图论中耳熟能详的 Floyd 算法。

题目

有 n 个城市，按从 0 到 n-1 编号。给你一个边数组 edges，其中 edges[i] = [fromi, toi, weighti] 代表 fromi 和 toi 两个城市之间的双向加权边，距离阈值是一个整数 distanceThreshold。

返回能通过某些路径到达其他城市数目最少、且路径距离 最大 为 distanceThreshold 的城市。如果有多个这样的城市，则返回编号最大的城市。

注意，连接城市 i 和 j 的路径的距离等于沿该路径的所有边的权重之和。

提示：

1
2
3
4
5
6
2 <= n <= 100
1 <= edges.length <= n * (n - 1) / 2
edges[i].length == 3
0 <= fromi < toi < n
1 <= weighti, distanceThreshold <= 10^4
所有 (fromi, toi) 都是不同的。

示例 1：

输入：n = 4, edges = [[0,1,3],[1,2,1],[1,3,4],[2,3,1]], distanceThreshold = 4
输出：3
解释：城市分布图如上。
每个城市阈值距离 distanceThreshold = 4 内的邻居城市分别是：
城市 0 -> [城市 1, 城市 2]
城市 1 -> [城市 0, 城市 2, 城市 3]
城市 2 -> [城市 0, 城市 1, 城市 3]
城市 3 -> [城市 1, 城市 2]
城市 0 和 3 在阈值距离 4 以内都有 2 个邻居城市，但是我们必须返回城市 3，因为它的编号最大。

示例 2：

输入：n = 5, edges = [[0,1,2],[0,4,8],[1,2,3],[1,4,2],[2,3,1],[3,4,1]], distanceThreshold = 2
输出：0
解释：城市分布图如上。
每个城市阈值距离 distanceThreshold = 2 内的邻居城市分别是：
城市 0 -> [城市 1]
城市 1 -> [城市 0, 城市 4]
城市 2 -> [城市 3, 城市 4]
城市 3 -> [城市 2, 城市 4]
城市 4 -> [城市 1, 城市 2, 城市 3]
城市 0 在阈值距离 2 以内只有 1 个邻居城市。

题解

算法：Floyd

如果我们知道图中每个点对 i, j 之间的最短距离，然后我们枚举所有的起点 u，就可以很容易知道从 u 开始在 distanceThreshold 步数之内可以到达多少个点，然后将可到达点数最少的点钟编号最大的返回即可。

记 d[i][j] 表示从 i 到 j 的最短路径。初始值为 INT_MAX / 2，表示 i, j 之间尚未发现路径。随着一轮一轮的迭代，d[i][j] 的值会进行更新，迭代完成后，d[i][j] 的值就是 i 到 j 的最短路径了，如果 d[i][j] 仍然为 INT_MAX / 2，则表示从 i 到 j 没有路径。

下面我看一下如何求出 d[i][j]，这也是 Floyd 算法解决的问题。该算法整体是一个动态规划算法，DP 推导过程就是从小的子图到大的子图最后到全图的过程。算法如下：

1
2
3
4
5
6
7
8
9
10
状态定义：
dp[k][i][j] := 在包含 0 ~ k 这 k 个点的子图上，点对 i, j 之间的最短路径。

初始化：
dp[0][i][j] = INT_MAX / 2
dp[0][i][i] = 0
dp[0][edge[0]][edge[1]] = edge[2]

状态转移：
dp[k][i][j] = min(dp[k-1][i][j], dp[k-1][i][k] + dp[k-1][k][j])

从动态规划的角度看，k 是 DP 问题的阶段，i, j 是附加状态，因此实现时 k 的循环需要放在 i, j 的循环的外面。

转移方程中 dp[k-1][i][j] 是在节点为 0,1,...,k-1 的子图中 i 到 j 的最短距离。此时考虑 k 点，在此前阶段中 i, j 之间的最短路径是不含 k 点的，在当前阶段把 k 点也引入，相当于 i, j 之间的最短路径可以使用的点的范围扩大了，因此推导阶段 k 的过程也称为松弛操作。

在当前阶段，最短路径的可选点集中增加了 k 点，dp[k-1][i][k] + dp[k-1][k][j] 是经过 k 点的新路径的长度，该路径从 i 出发，先以最短路径到 k （不在 0,1,...,k-1 的子图中，在前一阶段已经求出），然后从 k 再到 j 的过程类似。在扩展新点 k，也就是推导当前阶段时，可以复用此前阶段 0~k-1 的结果，这是动态规划的思想。

由于 dp[k][i][j] 只和 dp[k-1][...][...] 有关，通过滚动数组可以省略掉 k 这一维。

另外，使用 Floyd 算法很容易判断负环，只要在算法运行过程出现任意一个 dp[i][i] < 0，就说明有负环。因为 dp[i][i] 是从i出发，经过其他中转点绕一环回到自己的最短路径，所以如果 dp[i][i] < 0，就存在负环。

代码 (C++，模板)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution {
public:
    int findTheCity(int n, vector<vector<int>>& edges, int distanceThreshold) {
        vector<vector<int>> dp(n, vector<int>(n, INT_MAX / 2));
        for(const vector<int>& edge: edges)
        {
            dp[edge[0]][edge[1]] = edge[2];
            dp[edge[1]][edge[0]] = edge[2];
        }
        for(int i = 0; i < n; ++i)
            dp[i][i] = 0;
        for(int k = 0; k < n; ++k)
            for(int i = 0; i < n; ++i)
                for(int j = 0; j < n; ++j)
                    dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j]);
        int min_neighbor = n;
        int ans = n;
        for(int i = n - 1; i >= 0; --i)
        {
            int cnt = 0;
            for(int j = 0; j < n; ++j)
            {
                if(j == i) continue;
                if(dp[i][j] <= distanceThreshold)
                    ++cnt;
            }
            if(cnt < min_neighbor)
            {
                min_neighbor = cnt;
                ans = i;
            }
        }
        return ans;
    }
};
Share