Floyd-Warshall演算法

习题预习

1. 在无向图中，如何找出从给定源节点到所有其他节点的最短路径？
2. 在有向图中，如何找出所有节点彼此之间的最短路径？
3. 在有向图中，如何找出所有节点彼此之间的最长路径？
4. 在一个网格图中，如何找出所有格子之间的最短路径？
5. 在一个带权重的有向图中，如何找出从某个叶子节点到根节点的最短路径？

说明知识

Floyd-Warshall Algorithm（弗洛伊德-沃舍尔算法）是解决图中所有节点之间最短路径的经典算法之一，它是一种动态规划算法，以及解决所有点对之间最短路径的做法，同时也适用于带有负边权的图。

算法的基本思想是维护一个二维数组D，用来记录任意两点之间的最短路径长度。初始时，D[i][j]表示从节点i到节点j的距离，如果i和j不直接相邻，那么D[i][j]=正无穷。算法每进行一轮迭代，便会将D[i][j]和D[i][k]+D[k][j]（相当于以k作为中介）进行比较更新，最终得到任意两点之间的最短路径长度。

以下是弗洛伊德-沃舍尔算法的伪代码：

1. for k from 1 to |V|
2.      for i from 1 to |V|
3.          for j from 1 to |V|
4.              if D[i][j] > D[i][k] + D[k][j] then
5.                  D[i][j] = D[i][k] + D[k][j]

举例说明：
考虑下图：

构建邻接矩阵如下：

    1   2   3   4   5   6
  -------------------------
1 | 0   1   ∞   ∞   5   ∞
2 | ∞   0   1   ∞   ∞   ∞
3 | ∞   ∞   0   2   ∞   ∞
4 | ∞   ∞   ∞   0   ∞   1
5 | ∞   ∞   ∞   1   0   2
6 | ∞   ∞   ∞   ∞   ∞   0

其中，∞表示两点之间没有连通路径。

接下来，我们可以运用Floyd-Warshall Algorithm算法来求得任意两点之间的最短路径长度，具体过程如下：

第一轮迭代：k=1

D[1][2]=min(∞, ∞+1)=1, 
D[1][5]=min(5, ∞+1)=6,
D[2][3]=min(∞,∞+1)=1,
D[3][4]=min(∞,∞+2)=2,
D[4][6]=min(∞,∞+1)=1,
D[5][6]=min(∞,∞+2)=2

    1   2   3   4   5   6
  -------------------------
1 | 0   1   ∞   ∞   5   ∞
2 | ∞   0   1   ∞   ∞   ∞
3 | ∞   2   0   2   ∞   ∞
4 | ∞   ∞   ∞   0   ∞   1
5 | ∞   ∞   ∞   1   0   2
6 | ∞   ∞   ∞   ∞   ∞   0

第二轮迭代：k=2

D[1][3]=min(∞,1+1)=2,
D[1][6]=min(∞,5+2)=7,
D[2][4]=min(1,1+∞)=1,
D[3][6]=min(∞,2+2)=4,
D[4][5]=min(∞,1+2)=3

    1   2   3   4   5   6
  -------------------------
1 | 0   1   2   ∞   5   7
2 | ∞   0   1   2   ∞   3
3 | ∞   2   0   2   ∞   4
4 | ∞   ∞   ∞   0   3   1
5 | ∞   ∞   ∞   1   0   2
6 | ∞   ∞   ∞   ∞   ∞   0

第三轮迭代：k=3

D[1][4]=min(∞,2+2)=4,
D[2][5]=min(∞,1+2)=3,
D[3][6]=min(2,2+2)=2,
D[4][6]=min(1,3+1)=1,
D[5][3]=min(∞,2+2)=2

    1   2   3   4   5   6
  -------------------------
1 | 0   1   2   4   5   6
2 | ∞   0   1   2   3   3
3 | ∞   2   0   2   4   2
4 | ∞   ∞   ∞   0   3   1
5 | ∞   ∞   2   1   0   2
6 | ∞   ∞   ∞   ∞   ∞   0

第四轮迭代：k=4

D[2][6]=min(3,3+1)=3,
D[3][5]=min(2,2+4)=2,
D[4][2]=min(2,3+1)=2,
D[4][6]=min(1,3+1)=1,
D[5][1]=min(∞,2+5)=7

    1   2   3   4   5   6
  -------------------------
1 | 0   1   2   4   5   6
2 | ∞   0   1   2   3   3
3 | ∞   2   0   2   4   2
4 | ∞   2   3   0   3   1
5 | 7   6   2   1   0   2
6 | ∞   ∞   ∞   ∞   ∞   0

最终的结果是：

    1   2   3   4   5   6
  -------------------------
1 | 0   1   2   4   5   6
2 | ∞   0   1   2   3   3
3 | ∞   2   0   2   4   2
4 | ∞   2   3   0   3   1
5 | 7   6   2   1   0   2
6 | ∞   ∞   ∞   ∞   ∞   0

因此，我们可以得到所有点对之间的最短距离。例如，点1到点6的最短距离为6，点2到点1的最短距离为∞，点4到点5的最短距离为3 等。

总结：Floyd-Warshall Algorithm算法对有些权值为负的图仍然有效，并且由于操作矩阵，理论上算法时间复杂度为O(n^3)，适用于处理规模不是特别大的图，而且不受图形中负边权的影响，非常适合多源最短路径问题。

条列重点

1. Floyd-Warshall Algorithm（F-W算法）是一种动态规划算法，用于解决全源最短路问题。
2. F-W算法利用矩阵来存储每对节点之间的最短路长度。
3. 矩阵中每个元素的值代表从i到j的最短路长度，其中i和j是矩阵下标。
4. F-W算法每次更新矩阵中保存的最短路长度，以便找出每对节点之间的最短路。
5. F-W算法的核心思想是利用动态规划思想，将问题分解为子问题依次求解。
6. 在F-W算法中，我们先将图表示成一个带权有向图（即边带权），然后利用矩阵来保存最短路长度。
7. F-W算法主要包括初始化矩阵、遍历图、更新矩阵等步骤。
8. 尽管F-W算法的时间复杂度较高（为O(N^3)），但它可以处理带权有向图中任意两点之间的最短路问题，并且效果非常稳定。

知识测验

1. 给定一张有向带权图，求从任意一点到任意一点的最短路径。如果两点之间没有路径，输出inf。

程式码如下：
void Floyd() {
    for (int k = 1; k <= n; k++) {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (d[i][k] != INF && d[k][j] != INF && d[i][j] > d[i][k] + d[k][j]) {
                    d[i][j] = d[i][k] + d[k][j];
                }
            }
        }
    }
}

2. 给定一张无向带权图，求图中的最小生成树。如果图不连通，则输出-1。

程式码如下：
void Floyd() {
    for (int k = 1; k <= n; k++) {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (d[i][k] != INF && d[k][j] != INF && d[i][j] > d[i][k] + d[k][j]) {
                    d[i][j] = d[i][k] + d[k][j];
                }
            }
        }
    }
}

3. 给定一张有向带权图，求从任意一点到任意一点的最短路径，如果存在负权环，输出-1。

程式码如下：
int Floyd() {
    for (int k = 1; k <= n; k++) {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (d[i][k] != INF && d[k][j] != INF && d[i][j] > d[i][k] + d[k][j]) {
                    d[i][j] = d[i][k] + d[k][j];
                }
            }
        }
    }
    for (int k = 1; k <= n; k++) {
        if (d[k][k] < 0) { // 存在负权环
            return -1;
        }
    }
    return 0;
}

4. 给定一张有向带权图，求从每个点出发能到达的所有点之间的最小总权值和。

程式码如下：
void Floyd() {
    for (int k = 1; k <= n; k++) {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (d[i][k] != INF && d[k][j] != INF && d[i][j] > d[i][k] + d[k][j]) {
                    d[i][j] = d[i][k] + d[k][j];
                }
            }
        }
    }
    for (int i = 1; i <= n; i++) {
        int sum = 0;
        for (int j = 1; j <= n; j++) {
            if (d[i][j] != INF) {
                sum += d[i][j];
            }
        }
        printf("%d ", sum);
    }
}

5. 给定一张有向带权图，求从任意一点到任意一点经过正好k条边的最短路径。

程式码如下：
void Floyd(int k) {
for (int l = 1; l <= k; l++) { // l表示经过l条边
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
for (int m = 1; m <= n; m++) {
if (d[i][m] != INF && d[m][j] != INF && d[i][j] > d[i][m] + d[m][j]) {
d[i][j] = d[i][m] + d[m][j];
}
}
}
}
}
}