Floyd算法(多源汇最短路)

  • 简介：弗洛伊德于等人提出的解决任意两点之前最短路径的算法，也就是能解决多源最短路问题
  • 时间复杂度：O(n3)
  • 空间复杂度: O(n2) 邻接矩阵
  • 核心思想： 动态规划
  • 适用范围: 不含负权回路的稠密图多源汇最短路问题，可以处理负权边，不能判断是否存在负权回路
  • 核心代码:
//初始化
memset(dist, 0x3f, sizeof(dist));
for (int i = 1; i <= n; ++i) dist[i][i] = 0;
void floyd() {
    for (int k = 1; k <= n; ++k) 
        for (int i = 1; i <= n; ++i) 
            for (int j = 1; j <= n; ++j) 
                if (dist[i][k] != INF && dist[k][j] != INF) dist[i][j] = min(dist[i][j],dist[i][k] + dist[k][j]); 
}

/*
    1.理解三层循环(动态规划)
    2.dist[j][i] != INF && dist[i][k] != INF
    3.不能处理负权环或者负权回路
*/
#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
const int maxn = 210;
int dist[maxn][maxn];
int n ,m ,k, x, y, z;
inline void init() {
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if(i == j) dist[i][j] = 0;
            else dist[i][j] = 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 (dist[i][k] != INF && dist[k][j] != INF) dist[i][j] = min(dist[i][j],dist[i][k] + dist[k][j]); 
}
int main(void) {
    scanf("%d %d %d", &n, &m, &k);
    init();
    for (int i = 0; i < m; i++) {
        scanf("%d %d %d", &x, &y, &z);
        dist[x][y] = min(dist[x][y], z);
    }
    floyd();
    for (int i = 0; i < k; i++) {
        scanf("%d %d", &x, &y);
        if(dist[x][y] == INF) puts("impossible");
        else cout << dist[x][y] << endl;
    }
    return 0;
}

Q&A:

Q1：三层循环的顺序为什么是这样的呢？

A1：其实dist数组没有优化之前是三维的,dist[k][i][j]表示只以1到k中的点为中间点,点i到点j的最短距离，那么是如何进行状态转移的呢？
dist[k][i][j]可由两种状态转移而来：

  • 不经过k点dist[k - 1][i][j]；
  • 只经过k点，点i到点j的最短距离，那么可以表示为dist[k-1][i][k] + dist[k-1][k][j];
    所以dist[k][i][j] = min(dist[k-1][i][j], dist[k-1][i][k] + dist[k-1][k][j])， （i,j,k ∈[1,n])）;
    而上面的公式不能直接认为dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])， （i,j,k ∈[1,n])）;
    因为dist[i][k]跟dist[k][j]可能为第k-1层也可能为k层(更新以后)得证明一下,令j = k,可得d[k][i][k] = d[k-1][i][k], 令i = k,可得d[k][k][j] = d[k-1][k][j] 也就是说在第k-1阶段和第k阶段，点i和点k之间的最短路径长度是不变的,点j和点k之间的最短路径长度是不变的所以,所以更新前与更新后dist[i][k]跟dist[k][j]是相等的,那么可以把dist[i][k]跟dist[k][j]看成是第k-1层的,而易知dist[i][j]是上一层的所以可以用滚动数组做,即dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]),（i,j,k ∈[1,n])。判断是否可以用滚动数组关键是需要确保赋值号右侧的d[i][j], d[i][k]和d[k][j]的值是上一阶段（k-1阶段）的值,这里很显然d[i][j]是第k-1层的，所以只需证明d[i][k]与d[k][j]是k-1层的即可

Q2：为什么不能处理负权回路呢

  • A2：因为负权回路不存在最短路, 会一直绕着环更新值, 因为不存在最短路，所以这样算的结果也没啥意义。

Q3: 在floyd算法中为什么要判断d[i][k] != INF && d[k][j] != INF呢?

A3: 这里个人认为得加判断是否i跟k与k跟j是相通的，如果不判断的话确实最后会被一些数据给卡掉的比如,i-k是不连通的(距离为INF),但k-j是连通的但边权是负数,这样的话不断循环下去,d[i][k]可能会不断减小，一些题目可能减得不是很多还在一个数量级上，最后可以通过判断 d[i][k] 是否大于 INF / 2 等方式可以来判断i-k之间是否存在最短路径，但你是无法知道会减少到多少的,要是没有减少到同一个数量级,你怎么判断呢？所以说保险起见还是得判断if (dist[i][k] != INF && dist[k][j] != INF) dist[i][j] = min(dist[i][j],dist[i][k] + dist[k][j]);

参考