Floyd-Warshall算法原理及实现

Floyd-Warshall算法，或者简称为Floyd算法，是一种方便好写的全图最短路算法，适用于求全图任意点对最短路的情况下，复杂度较高。下面介绍该算法的原理及实现细节。

Floyd算法是一种运用动态规划思想求最短路的经典算法，因此读者需要以动态规划的思想来理解该算法的流程。
对于给定的一个图，我们需要得到它的任意点对最短路结果，以数组dis(u,v)来表示点u到点v的最短路距离。
为了使问题简化，我们规定，给定的图中无自环与重边。
最初，我们需要给这个数组设置初始值。对于图中的任意点u，dis(u,u)=0。对于图中的任意有向边(u,v,w)，dis(u,v)=w。其他的点对值设置为∞。
随后，我们需要枚举“跳板”点k，寻找是否存在一条由(u,k)与(k,v)两条路径拼成的比当前找到的最短路更短。在这里，我们用三重循环，首先枚举k，再枚举点对(u,v)，并用以下方程对(u,v)进行松弛操作。
dis(u,v)=mink∈G{dis(u,k)+dis(k,v)}
完成以上步骤后，dis数组中的结果即是我们需要的全图最短路了。

复杂度分析

算法流程中，三重循环的位置是复杂度最高的一部分，由于枚举k进行|V|次，而枚举点对(u,v)进行|V|2次，该算法的复杂度为O(|V|3)。注：V表示图G中的点集。

算法的扩展应用

如果我们令dis数组的初值全设为0，进行Floyd算法后，如果存在点u满足dis(u,u)<0，则说明u点在一个负环中。

存在重边、自环时的处理方法

自环如为正边可不必加入该边，如为负边则存在负环。
重边只保留权值最小边即可。
实现中，通用的处理方法为设置dis数组为点对间的最短边即可。

下面是一种Floyd算法在C++语言中的实现方法。
输入格式、输出格式、数据范围等参见代码。

// Code by KSkun, 2019/1
#include <cstdio>
#include <cctype>
#include <cstring>

#include <algorithm>

typedef long long LL;

inline char fgc() {
    static char buf[100000], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2)
        ? EOF : *p1++;
}

inline LL readint() {
    LL res = 0, neg = 1; char c = fgc();
    for(; !isdigit(c); c = fgc()) if(c == '-') neg = -1;
    for(; isdigit(c); c = fgc()) res = res * 10 + c - '0';
    return res * neg;
}

inline char readsingle() {
    char c;
    while(!isgraph(c = fgc())) {}
    return c;
}

const int MAXN = 105, INF = 0x3f3f3f3f;

int n, m;
int dis[MAXN][MAXN];

inline void addedge(int u, int v, int w) {
    dis[u][v] = std::min(dis[u][v], w);
}

inline void init() {
    memset(dis, 0x3f, sizeof(dis));
    for(int i = 1; i <= n; i++) dis[i][i] = 0;
}

inline void floyd() {
    for(int k = 1; k <= n; k++) {
        for(int i = 1; i <= n; i++) {
            for(int j = 1; j <= n; j++) {
                dis[i][j] = std::min(dis[i][j], dis[i][k] + dis[k][j]);
            }
        }
    }
}

int main() {
    n = readint(); m = readint();
    init();
    for(int i = 1, u, v, w; i <= m; i++) {
        u = readint(); v = readint(); w = readint();
        addedge(u, v, w);
    }
    floyd();
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= n; j++) {
            printf("%d ", dis[i][j] >= INF ? -1 : dis[i][j]);
        }
        putchar('\n');
    }
    return 0;
}

关于循环顺序

为什么要先枚举k，而后枚举点对(u,v)，这是一个困扰很多初学者的问题。
我们考虑调换循环顺序，先枚举u，而后枚举k和v，你会发现，如果以这样的顺序松弛，存在(u,k)或(k,v)在松弛了(u,v)之后再被松弛为一个更小的值的情况。
例如，这里有一个例子：

（图片来自Wikipedia，使用CC0协议授权使用）
容易发现，在松弛(1,2)并以3为“跳板”时，而如果调换了循环顺序，在松弛该点时，(3,2)还未松弛，所以松弛操作失败，容易发现，点3在(1,2)的最短路径上，所以上面的松弛失败是异常的。有时，这种失败可能不会影响到答案，但当路径较长的时候，结果错误会影响答案。
因此，读者应当牢记循环的顺序，以避免使用算法时发生这类错误。

退役了还让我写OI技术类文章，我看你是在难为我胖虎QAQ。
不过突然被人问到了Floyd算法的循环顺序问题，才想起来OI生涯中并没好好思考过这个问题。找了一些资料和示例算是想明白了，也觉得自己这样半吊子学算法不太行，于是把这部分内容补到了这篇文章之中。也算是一种对自己的提醒和不忘初心的追求吧。
一个半吊子OIer能混到今天这个程度，该算是我的幸运还是悲哀呢？