Floyd详解

先来看一组样例

Input

5 8
1 4 5
1 3 2
3 4 3
4 2 2
4 5 1
1 5 8
2 5 4
3 2 6

Output

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

我们先将dis全部变成极大值（很重要）

但是如果i = j，dis[i][j] = 0;

我们不妨顺着代码的执行来手动模拟一下（前方高能！！！）

这个可真难画，将就着看吧。

k = 1 :

以1为中间节点来扩展

按照代码中写的来看，我们看到以1为中间节点可以扩展出从1到3，1到4，1到5的值。

此时已经没有点可以与1相连。

以2为中间节点的时候，这时候1和2还不能直接相连。所以不能扩展。

再看别的能扩展的i 和 j，

如下图我们可以更新3->2->5和4->2->5;

k = 3 :

从1到2的路径为极大值，如果通过3到达2，长度为8，8<=INF，所以dis[1][2]更新成8。

同理，dis[1][4] = 5;

此时，以3为中间节点的操作已经完成。

后面就不画图了，自行脑补吧

 k = 4 :

可以通过4更新1->4->5 , 3->4->5 , 1->4->2 , 3->4->2.

同理，我们就可以把所有的点都更新完。

完整代码

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#define INF 214748364

using namespace std;

int n, m, s, t;
int dis[1005][1005];

int main() {
    scanf("%d%d", &n, &m);
    for(int i=1; i<=n; i++) {
        for(int j=1; j<=n; j++) {
            dis[i][j] = (i == j)?0:INF;
        }
    }
    for(int i=1; i<=m; i++) {
        int u, v, w;
        scanf("%d%d%d", &u, &v, &w);
        dis[u][v] = w;
    }
    for(int k=1; k<=n; k++) {
        for(int i=1; i<=n; i++) {
            for(int j=1; j<=n; j++) {
                if(dis[i][j] > dis[i][k]+dis[k][j]) {
                    dis[i][j] = dis[i][k]+dis[k][j];
                }
            }
        }
    }
    for(int i=1; i<=n; i++) {
        for(int j=1; j<=n; j++) {
            if(dis[i][j] != INF) printf("%d ", dis[i][j]);
            else printf("-1 "); 
        }
        printf("
");
    }
}

作者：wlz

出处：http://www.cnblogs.com/bljfy/p/8696334.html 

本文版权归作者和博客园共有，欢迎转载，但未经作者同意必须保留此段声明，且在文章页面明显位置给出原文连接，否则保留追究法律责任的权利。