弗洛伊德算法

介绍

弗洛伊德算法（Floyd 算法），用于求任意两节点最短路，相比迪杰斯特拉算法时间复杂度较高，但易实现。适用于任何图，不管有向无向，边权正负，但是最短路必须存在。（不能有负环）

图示

先将图转换为邻接矩阵
Floyd 算法需要对图中每一个节点进行维护，更新其他节点经过该节点抵达另外节点的距离，使得该距离最小。

例如，第一次更新A节点，B经过A到C的距离为2+3，B经过A到D的距离为2+6，C经过A到D的距离为3+6。
又因为C到D邻接矩阵的距离为2小于9，因此不更新C到D的边。添加新边BC、BD，因为当前邻接矩阵不可达，更新邻接矩阵。

依次类推，当最后一个节点F更新完成后，算法结束，邻接矩阵内更新为最短路径。

算法示例

void Floyd(vector<vector<int>>&f, int n){
    for (k = 0; k < n; k++) {
        for (x = 0; x < n; x++) {
            for (y = 0; y < n; y++) {
                f[x][y] = min(f[x][y],f[x][k]+f[k][y]);
            }
        }
    }
}

其中 f 为邻接矩阵，n 为节点个数。

---

算法分析

1. 时间复杂度 $O(n^3)$
2. 空间复杂度 $O(n^2)$

---

例题

1. leetcode 743.网络延迟时间