概述

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

算法原理

流程

Floyd算法是一种运用动态规划思想求最短路的经典算法，因此读者需要以动态规划的思想来理解该算法的流程。
对于给定的一个图，我们需要得到它的任意点对最短路结果，以数组$dis(u, v)$来表示点$u$到点$v$的最短路距离。
为了使问题简化，我们规定，给定的图中无自环与重边。
最初，我们需要给这个数组设置初始值。对于图中的任意点$u$，$dis(u, u) = 0$。对于图中的任意有向边$(u, v, w)$，$dis(u, v) = w$。其他的点对值设置为$\infty$。
随后，我们需要枚举“跳板”点$k$，寻找是否存在一条由$(u, k)$与$(k, v)$两条路径拼成的比当前找到的最短路更短。在这里，我们用三重循环，首先枚举$k$，再枚举点对$(u, v)$，并用以下方程对$(u, v)$进行松弛操作。
$$ dis(u, v) = \min_{k \in 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能混到今天这个程度，该算是我的幸运还是悲哀呢？

参考资料

• Floyd–Warshall algorithm – Wikipedia
• Floyd-Warshall All-Pairs Shortest Path
• 关于Floyd算法三重循环顺序的问题 – shan_mx的博客 – CSDN博客