初识Floyd算法 7月7日 【今日算法】

Floyd 算法

Floyd 算法又称插点法，它的核心思想是动态规划，常用来求解图中任意一对顶点之间的最短路径问题。

算法步骤

1. 首先定义一个距离矩阵D[n][n]，其中D[i][j]表示，顶点i到顶点j的距离。
2. 然后通过已知条件初始化距离矩阵D[n][n]。
3. 图中 n 个顶点依次作为插入点，更新距离矩阵。例如，k 为其中一个顶点，D[i][k] + D[k][j] < D[i][j]，那说明顶点i经过顶点k再到达j，比直接到达j要近。所以更新D[i][j]：D[i][j] = D[i][k] + D[k][j]。
4. 可以归纳得到状态转移方程：D[i][j] = min(D[i,k]+D[k,j],D[i,j]);

Floyd 核心代码：

// Floyd算法
for (int k = 0; k < n; k++) {
// n个顶点依次作为插入点
// 注意插点k是放在第一层循环，后面会解释原因
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            // 遍历各个顶点之间的距离，并用插入点进行更新
            D[i][j] = min(D[i][k]+D[k][j], D[i][j]);
        }
    }
}

题型讲解

1334. 阈值距离内邻居最少的城市

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

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

示例

输入：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，因为它的编号最大。

题目解析

1. 使用 Floyd 算法求出各个城市到其它城市的距离，保存在矩阵D[n][n]中。
2. 遍历D[n][n]，统计各个城市在距离不超过 distanceThreshold 的情况下，能到达的其它城市的数量。
3. 返回能到达其它城市数量最少的城市 ret。

解题代码

class Solution {
public:
    int findTheCity(int n, vector<vector<int>>& edges, int distanceThreshold) {
        // 定义二维D向量，并初始化各个城市间距离为INT_MAX（无穷）
        vector<vector<int>> D(n, vector<int>(n, INT_MAX));
        // 根据edges[][]初始化D[][]
        for (auto& e : edges) {
        // 无向图两个城市间的两个方向距离相同
            D[e[0]][e[1]] = e[2];
            D[e[1]][e[0]] = e[2];
        }
        // Floyd算法
        for (int k = 0; k < n; k++) {
        // n个顶点依次作为插入点
            for (int i = 0; i < n; i++) {
                for (int j = i+1; j < n; j++) {
                    if (D[i][k] == INT_MAX || D[k][j] == INT_MAX) {
                    // 这些情况都不符合下一行的if条件，
                    // 单独拿出来只是为了防止两个INT_MAX相加导致溢出
                        continue;
                    }
                    D[i][j] = min(D[i][k]+D[k][j], D[i][j]);
                    D[j][i] = D[i][j];
                }
            }
        }
        // 选择出能到达其它城市最少的城市ret
        int ret;
        int minNum = INT_MAX;
        for (int i = 0; i < n; i++) {
            int cnt = 0;
            for (int j = 0; j < n; j++) {
                if (i != j && D[i][j] <= distanceThreshold) {
                    cnt++;
                }
            }
            if (cnt <= minNum) {
                minNum = cnt;
                ret = i;
            }
        }
        return ret;
    }
};

答疑

为什么遍历插入点 k 是放在第一层循环？

这个源自 Floyd 的核心思想--动态规划，代码中的二维状态转移方程D[i][j] = min(D[i,k]+D[k,j],D[i,j]);，其实是从三维简化得到的。

我们不妨从最初的三维说起，思路和二维一样：

1. 首先定义状态数组（也就是距离矩阵）D[n][n][n]，其中D[k][i][j]表示顶点i, 顶点j通过前k个顶点（0~k）得到的最短距离。
2. D[k][i][j]是从D[k-1][i][j]和D[k-1][i][k] + D[k-1][k][j]两者中值较小的一个转移得到的，也就是说要在前k-1个顶点已经插入，更新距离矩阵状态之后，第k个顶点才能作为插入顶点。
3. 归纳得到状态转移方程：D[k][i][j] = min(D[k-1][i][j], D[k-1][i][k] + D[k-1][k][j])。
4. 其中k的作用是标志到达了第几个插入点，也就是状态数组到达了哪个状态，不用刻意记录，于是减去第一维就变成了二维。

明白了 Floyd 的三维 dp 思想，根据状态转移方程在编码时就很自然的会将 k 放在第一层循环，而将k放在最后一层则是错误的编码。

题解代码还能怎么优化

因为两个城市之间是互通的，也就是无向图，那计算出了D[i][j]就没必要重复计算D[j][i]了，于是我们可以把 Floyd 算法的最后一层循环的j 改成从i+1 开始计数，同时在计算出D[i][j]后直接赋值给D[j][i]。

// Floyd算法
for (int k = 0; k < n; k++) {
    // n个顶点依次作为插入点
    for (int i = 0; i < n; i++) {
        for (int j = i+1; j < n; j++) {
            if (D[i][k] == INT_MAX || D[k][j] == INT_MAX) {
                // 这些情况都不符合下一行的if条件，
                // 单独拿出来只是为了防止两个INT_MAX相加导致溢出
                continue;
            }
            D[i][j] = min(D[i][k]+D[k][j], D[i][j]);
            D[j][i] = D[i][j];
        }
    }
}

最后

感谢您的观看！希望您能有所收获。

来源 | 小小算法

作者 | 小小算法