LaneBlog

蝼蚁虽小,也有梦想

PHP Socket服务 | PHP微信开发框架 | 开源博客

    

   任意两点最短路径被称为多源最短路径,即给定任意两个点,一个出发点,一个到达点,求这两个点的之间的最短路径,就是任意两点最短路径问题,多源最短路径,而Floyd-Warshall算法最简单,只有5行代码,即可解决这个问题。

    比如三个城市,城市1,城市2,城市3。从城市1到城市3需要10公里,从城市1到城市2需要3公里,从城市2到城市3需要4公里,如下图:

4F966EED-1AD1-4FD9-ABB4-0448137A13E4.png


那么从城市1到城市3,如何走更近?1到3是直达,但是却10公里,而1到2到3,虽然转一下,但是距离短了,只要7公里。

这就引出了我们的观念,一个点到另一个点要变短,就要引入第三个点,甚至第四个点,第五个点。


假设在map数组里存储了点i到点j的距离map[i][j],那么我们引入第三个点k,则如果点i到点j的距离比点i到点k加点k到点j,则点i到点j的最短距离是点i到点k加点k到点j。

即如果map[i][j]<map[i][k]+map[k][j],则map[i][j]=map[i][k]+map[k][j]


这就是Floyd-Warshall算法。核心代码如下:

//只能从k中转

    for(k=1; k<=cityCount; k++){

        //从i出发

        for(i=1; i<=cityCount; i++){

            //到j结束

            for(j=1; j<=cityCount; j++){

                if(map[i][j] > (map[i][k] + map[k][j])){

                    map[i][j] = map[i][k]+ map[k][j];

                }

            }

        }

    }

三个for循环,加一个if,加一个赋值,简简单单的五行代码,就实现了任意一个点到任意另一个点的最短距离。

显而易见,时间复杂度是O(n3).


完整代码如下

#include <stdio.h>

int map[11][11] = {{0}};

int book[11] = {0};

int main(){

    int i, j, k, cityCount, roadCount, length, x, y;

    scanf("%d %d", &cityCount, &roadCount);

    for(i=1; i<=cityCount; i++){

        for(j=1; j<=cityCount; j++){

            map[i][j] = 0;

        }

    }

    for(i=1; i<=roadCount; i++){

        scanf("%d %d %d", &x, &y, &length);

        map[x][y] = length;

    }

    //只能从k中转

    for(k=1; k<=cityCount; k++){

        //i出发

        for(i=1; i<=cityCount; i++){

            //j结束

            for(j=1; j<=cityCount; j++){

                if(map[i][j] == 0 || map[i][k] == 0 || map[k][j] == 0) continue;

                if(map[i][j] > (map[i][k] + map[k][j])){

                    map[i][j] = map[i][k]+ map[k][j];

                }

            }

        }

    }

    //现在的map里就是从一个点i到另一个点j的最短距离map[i][j]

    printf("点1到点5的最短路径是:%d", map[1][5]);

}


输入

5 8

1 2 3

1 3 2

1 5 10

2 3 1

3 5 3

3 4 5

4 5 1

2 4 8


输入,5

©2014 www.lanecn.com , All rights reserved. Power By Li Xuan.  京ICP备14005030号