首页 > 代码库 > 多源最短路径---Floyd-Warshall算法

多源最短路径---Floyd-Warshall算法

摘自啊哈算法-知识分享,代码自己有改动,使得输出更直观。

小哼准备去一些城市旅游。有些城市之间有公路,有些城市之间没有,如下图。为了节省经费以及方便计划旅程,小哼希望出发之前知道任意两个城市之间的最短路程。

技术分享

上图中有四个城市8条公路,公路上的数字表示该公路的长短。现在需要求任意两个城市之间的最短路径,也就是求任意两点之间的最短路径。“多源路径最短”问题

现在需要一个数据结构来存储图的信息,用一个4*4的矩阵来存储。比如城市1到城市2的路程为2,则设e[1][2]的值为2。2号城市无法到达城市4,则设置e[2][4]的值为无穷。另外此处约定一个城市自己到自己的路程为0。

问题:如何求任意两点之间的最短路径?

通过之前的学习,深度优先搜索或者广度优先搜索可以求出两点之间的最短路径。所以进行n平方遍深度或者广度优先搜索,即对每两个点都进行一次深度或者广度优先搜索,便可以求出任意两点的最短路径。but,代码可读性差。

这里,采用Floyd-Warshall算法,只有五行代码的算法进行计算。

基本思想:最开始只允许经过1号顶点进行中转,接下来只允许经过1号和2号顶点进行中转.......允许经过1~n号顶点进行中转,求任意两点之间的最短路径。

用一句话概括:从i号顶点到j号顶点只经过前k号顶点的最短路程。其实这是一种“动态规划”的思想。

Floyd-Warshall算法核心代码是:

for (k = 1; k <= n; k++) //k代表i到j间的任一点
  for (i = 1; i <= n; i++)
   for (j = 1; j <= n; j++)
    if (e[i][k]<inf && e[k][j]<inf && e[i][j]>e[i][k] + e[k][j])
     e[i][j] = e[i][k] + e[k][j];
下面给出这个算法的完整代码及其输出结果:

完整代码:

 

/*Floyd-Warshall算法 佛洛依德-沃舍尔*/
#include<stdio.h>

int main()
{
    int i, j, k, n, m;
    int e[10][10];
    int t1, t2, t3;
    int inf = 99999999; //如果有100条边,则正无穷只需用10001表示,就比10000多1即可。
    //读入n和m,n表示顶点个数,m表示边的个数
    scanf_s("%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_s("%d %d %d", &t1, &t2, &t3);
        e[t1][t2] = t3;
    }
    //输出开始数据矩阵
    printf("初始的路径矩阵:\n");
    printf(" ");
    for (i = 1; i <= n; i++)
        printf("%10d", i);
    printf("\n");
    for (i = 1; i <= n; i++)
    {
        printf("%d", i);
        for (j = 1; j <= n; j++)
        {
            printf("%10d", e[i][j]);
        }
        printf("\n");
    }
    //Floyd-Warshall算法核心语句
    for (k = 1; k <= n; k++) //k代表i到j间的任一点
        for (i = 1; i <= n; i++)
            for (j = 1; j <= n; j++)
            {
                //如果正无穷与另一个值相加大于正无穷不被允许,
                //则需要多加上前两个条件
                if (e[i][k]<inf && e[k][j]<inf && e[i][j]>e[i][k] + e[k][j]) 
                    e[i][j] = e[i][k] + e[k][j];
            }
    //输出最终结果
    printf("Floyd-Warshall的最短路径矩阵:\n");
    printf(" ");
    for (i = 1; i <= n; i++)
        printf("%10d", i);
    printf("\n");
    for (i = 1; i <= n; i++)
    {
        printf("%d", i);
        for (j = 1; j <= n; j++)
        {
            printf("%10d", e[i][j]);
        }
        printf("\n");
    }
    return 0;
}

 

 

 

输出结果:

技术分享

注意:此处无穷用99999999代替。

多源最短路径---Floyd-Warshall算法