Shouyu

Appearance

Floyd算法 ​

题目描述 ​

小明喜欢去公园散步，公园内布置了许多的景点，相互之间通过小路连接，小明希望在观看景点的同时，能够节省体力，走最短的路径。

给定一个公园景点图，图中有 N 个景点（编号为 1 到 N），以及 M 条双向道路连接着这些景点。每条道路上行走的距离都是已知的。

小明有 Q 个观景计划，每个计划都有一个起点 start 和一个终点 end，表示他想从景点 start 前往景点 end。由于小明希望节省体力，他想知道每个观景计划中从起点到终点的最短路径长度。 请你帮助小明计算出每个观景计划的最短路径长度。

题目链接：https://kamacoder.com/problempage.php?pid=1155

文章讲解：https://programmercarl.com/kamacoder/0097.小明逛公园.html

思考 ​

本题是多源最短路径问题

求多个起点到多个终点的多条对段路径。

正负权值都可以处理。

核心思想是动态规划。

求节点1到节点9的最短路径中间可能经过节点5也可能不经过。

如果经过，那么那 节点1 到 节点9 的最短距离 是不是可以由 节点1 到节点5的最短距离 + 节点5到节点9的最短距离组成。即

grid[1][9] = grid[1][5] + grid[5][9]。

那么节点1到节点5的最短路径怎么求？grid[1][5]？。

比如节点1到节点5的最短路径就可以由节点1 到 节点3的最短距离 + 节点3 到 节点5 的最短距离组成呢？

即 grid[1][5] = grid[1][3] + grid[3][5]

这就是我们的递推关系。

节点1 到 节点9 的最短距离 可以由 节点1 到节点5的最短距离 + 节点5到节点9的最短距离组成， 也可以由 节点1 到节点7的最短距离 + 节点7 到节点9的最短距离的距离组成。

那么选哪个呢？

是不是 要选一个最小的，毕竟是求最短路。

动规五部曲 ​
1、确定dp数组及下标含义 ​

grid[i][j][k] = m，表示 节点i 到 节点j 以[1...k] 集合中的一个节点为中间节点的最短距离为m。这里的 k 表示从i到j可能经过的中间节点是1-k中的其中任何一个。

2、递推公式

  1. 节点i 到 节点j 的最短路径经过节点k
  2. 节点i 到 节点j 的最短路径不经过节点k

对于第一种情况，grid[i][j][k] = grid[i][k][k - 1] + grid[k][j][k - 1]

第二种情况，grid[i][j][k] = grid[i][j][k - 1]

最短路，那么取最小值：

grid[i][j][k] = min(grid[i][k][k - 1] + grid[k][j][k - 1]， grid[i][j][k - 1])

3、初始化

从递推公式上看有 k-1，那么就必须考虑k等于0的情况。另外i,j都不依赖于i-1,j-1。所以不管i和j，只需要初始化所有的gird[i][j][0]就行了。

如何初始化？

gird[i][j][0]其实也可以理解为从节点i到节点j中间不经过任何结点的最小距离。

即直接相连的两个节点。而那些输入中没有给的，即不直接相连的节点，之间的距离设置为极大值即可。本题求的是最小值，所以输入数据没有涉及到的节点的情况都应该初始为一个最大数。

4、遍历顺序

而 k 依赖于 k - 1， i 和j 倒 并不依赖与 i - 1 或者 j - 1 等等。

把 gird 这个三位数组看作三维立方体，i和j是平层，k垂直向上。便利的顺序是从底部一层层向上遍历。至于先i还是先j，无所谓。

5、打印dp数组

三位数组不太好打印。

空间优化 ​

可以发现k只依赖于k-1，不依赖于k-2、k-3以后，那么没必要存n层。只需要两层即可

只需要记录 grid[i][j][1] 和 grid[i][j][0] 就好，之后就是 grid[i][j][1] 和 grid[i][j][0] 交替滚动。

进一步，两层还不够，能变为一层吗？

从递推公式上看

C++
如果 本层刚计算好的 grid[i][k] 比上一层 （即k-1层）计算的 grid[i][k] 小，说明确实有 i 到 k 的更短路径，那么基于 更小的 grid[i][k] 去计算 gird[i][j] 没有问题。

如果 本层刚计算好的 grid[i][k] 比上一层 （即k-1层）计算的 grid[i][k] 大， 这不可能，因为这样也不会做更新 grid[i][k]的操作。

所以递推公式可以是

C++
grid[i][j] = min(grid[i][j], grid[i][k] + grid[k][j]);

其实也可以这样理解，对于每个节点k，尝试通过节点k的更新自动更新所有节点i到节点j的距离。如果 dist[i][j] 大于 dist[i][k] + dist[k][j]，则更新dist[i][j]。

二维数组版本

C++
#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n, m, p1, p2, val;
    cin >> n >> m;

    vector<vector<int>> grid(n + 1, vector<int>(n + 1, 10005));  // 因为边的最大距离是10^4

    for(int i = 0; i < m; i++){
        cin >> p1 >> p2 >> val;
        grid[p1][p2] = val;
        grid[p2][p1] = val; // 注意这里是双向图

    }
    // 开始 floyd
    for (int k = 1; k <= n; k++) {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                grid[i][j] = min(grid[i][j], grid[i][k] + grid[k][j]);
            }
        }
    }
    // 输出结果
    int z, start, end;
    cin >> z;
    while (z--) {
        cin >> start >> end;
        if (grid[start][end] == 10005) cout << -1 << endl;
        else cout << grid[start][end] << endl;
    }
}

复杂度 ​

  • 时间复杂度： O(n^3)
  • 空间复杂度：O(n^2)

floyd复杂度比较高，适合稠密图，源点多的角度。

如果源少，多次dijkstra也行。