Floyd-Warshall算法(最短距离)

Robert W.Floyd和Stephen Warshall在1962年发表了Floyd-Warshall算法

 

如图，有1234，四个点，每个点都有一定的距离，比如1和2有2的距离，现在我想知道任意两个点的最短距离。

 

我先用“邻接矩阵存储法”将这个图转化为矩阵

 竖坐标是出发点，横坐标是目的地，∞表示无穷大，也就是到不了，例如2到不1。有了这个矩阵，就可以用一个两维数组来存储。

 

现在切入重点：Floyd-Warshall算法。
拿从4到3来看，4到3直达为12，要想缩短，只有“换乘”。

我发现4还可以直达1，1换乘到3，这时距离为11，比直达要短。那有什么比这个还短的？到1时再换乘!不要走直达。我发现1可以到2，2换乘到3，这时距离为10，又短了。

 

我发现每个点都可以作为“换乘点”，先初始化直达的距离，再把1作为“换乘点”，计算出新的最短距离，再把1和2作为“换乘点”。。。最后1234全作为“换乘点”。这就是Floyd-Warshall算法的基本思想，现在上代码：

 

#include <stdio.h>
int main()
{
    int a[10][10], n, m, i, j, k, t1, t2, t3;

    int inf = 99999999;//这里定义的正无穷

    //读入nm,n为顶点数，m为边的条数
    scanf("%d %d", &n, &m);

    //初始化矩阵
    for (i = 1; i <= n; i++)
        for(j = 1; j <= n; j++)
            if(i == j)a[i][j] = 0;
            else a[i][j] = inf;


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

    //Floyd-Warshall算法核心代码
    for(i = 1; i <= n; i++)
        for(j = 1; j <= n; j++)
            for(k = 1; k <= n; k++)
                if(a[j][i] < inf && a[i][k] < inf && a[j][k] > a[j][i] + a[i][k])
                    a[j][k] = a[j][i] + a[i][k];

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

 输入：

 

 

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

 Floyd-Warshall算法思路貌似很复杂，但它的核心代码只有五行，时间复杂度是O(N3)，如果我只想知道某一个点到其它点的最短距离，用这套算法就感觉太耗时了。算法发表者Robert W.Floyd也是图灵奖的获得者（屌爆了）。