最短路径 只有五行的算法——Floyd-Warshall

最短路径 只有五行的算法——Floyd-Warshall

输入:

4 8
1 2 2
1 3 6
1 4 4
2 3 3
3 1 7
3 4 1
4 1 5
4 3 12

输出：

0         2         5         4
9         0         3         4
6         8         0         1
5         7        10         0

题解：

#include<stdio.h>
int main(){
    int e[10][10], k, i, j, n, m, t1, t2 ,t3;
    int inf = 99999999; // 用inf（infinity的缩写）存储一个我们认为的正无穷值
    //读入n和m， n表示顶点个数， m表示边的条数
    scanf("%d %d",&n, &m);

    //初始化
    for (i = 1; i <= n ; i ++){
        for (j = 1 ; j <= n ; j ++){
            if (i == j) e[i][j] = 0;
            else e[i][j] = inf;
        }
    }

    //读入边
    for (i = 1; i <= m ;i ++){
        scanf("%d %d %d",&t1, &t2, &t3);
        e[t1][t2] = t3;
    }

    //Floyd-Warshall算法核心语句
    for (k = 1 ; k <= n ; k ++)
        for (i = 1 ; i <= n ; i ++)
            for (j = 1 ; j <= n ; j ++)
                if (e[i][j] > e[i][k] + e[k][j])
                    e[i][j] = e[i][k] + e[k][j];

    //输出最终的结束
    for (i = 1 ; i <= n ; i ++){
        for (j = 1 ; j <= n ; j ++){
            printf("%10d", e[i][j]);
        }
        printf("\n");
    }
}

运行结果：