5行代码搞定floyd算法

た入场券 2022-05-21 07:35 207阅读 0赞

## 简介 ##

floyd是图搜算法中很经典的一个算法，用于求一副图中任意两点之间的最短路径（时间，花费等）。其算法思想感觉比Dijkstra简单，而且代码也很容易实现。不过就是效率比较低，三个for循环导致复杂度为O（n3)。

## 实例 ##

假如有如下的地图，图中四个点代表不同的城市，带箭头的边表示各城市间的航线（城市1可以飞到城市2，但城市2不可直接飞到城市1，只能通过其他城市周转），航线附近的数字为机票价格。  
![这里写图片描述][70]  
我们利用二维矩阵存储这幅地图的各个城市和每条航线的信息。  
比如1号城市到2号城市的机票为2元，则设graph\[1\]\[2\]的值为2。2号城市无法到达4号城市，则设置graph\[2\]\[4\]的值为∞（自己设定一个较大的值即可）。另外此处约定一个城市自己飞到自己的票价为0，例如graph\[1\]\[1\]为0，具体如下：  
![这里写图片描述][70 1]  
那么如何求任意城市之间最少的机票开销呢？  
其实思想很简单，就是通过一个中间城市周转一下。例如从城市1直接飞到城市3需要6元，但是可以选择先从城市1飞到城市2（2元），再从城市2飞到城市3（3元），这样只需要花费2+3=5元即可。  
同理，从城市4直接飞到城市3机票需要12元，而可以选择先从4飞到1（5元），再从1飞到3（6元），花费降到5+6=11元。为了省1块钱，旅途要波折一点。  
如果为了丧心病狂地省钱，不怕麻烦，甚至可以先从城市4飞到城市1，然后从1飞到2，再从2飞到3，这样只需要5+2+3=10块钱，比4直飞3的12块整整省了2元。

## 算法思想 ##

所以，如果要让任意两个城市（例如从顶点a点到顶点b）之间的开销变少，只能引入第三个城市（顶点k），并通过这个顶点k中转即a->k->b，才可能缩短原来从顶点a点到顶点b的开销。那么这个中转的顶点k是1~n中的哪个点呢？甚至有时候不只通过一个点，而是经过两个点或者更多点中转开销则会更少，即a->k1->k2->b或者a->k1->k2…->ki->……->b。

如果现在只允许经过1号城市，求任意两个城市之间的最低票价，应该如何求呢？只需判断graph\[i\]\[1\]+graph\[1\]\[j\]是否比graph\[i\]\[j\]要小即可。graph\[i\]\[j\]表示的是从i号城市到j号城市之间的机票花费。graph\[i\]\[1\]+graph\[1\]\[j\]表示的是从i号城市先到1号城市，再从1号城市到j号城市的票价之和。其中i是1~n循环，j也是1~n循环，代码实现如下：

for(i = 1;i <= n;i++) {   
        for(j = 1;j <= n;j++) {   
            if ( graph[i][j] > graph[i][1] + graph[1][j] )   
                graph[i][j] = graph[i][1] + graph[1][j];   
        }   
    }

在只允许通过1号城市周转的情况下，任意两个城市之间的最低机票花费更新为：  
![这里写图片描述][70 2]  
由上图可知：在只通过1号城市中转的情况下，3号城市到2号城市（graph\[3\]\[2\]）、4号城市到2号城市（graph\[4\]\[2\]）以及4号城市到3号城市（graph\[4\]\[3\]）的票价开销都变少了。

接下来继续求在只允许经过1和2号两个城市中转的情况下任意两点之间的最低票价。此时只需要在经由1号城市周转的结果之下，加入2号城市，再判断如果经过2号城市是否可以使得i号城市到j号城市之间的票价变得更少。即判断graph\[i\]\[2\]+graph\[2\]\[j\]是否比graph\[i\]\[j\]要小，代码实现为如下：

//经过1号顶点   
    for(i=1;i<=n;i++)   
        for(j=1;j<=n;j++)   
             if (graph[i][j] > graph[i][1]+graph[1][j])
                   graph[i][j]=graph[i][1]+graph[1][j];   
    //经过2号顶点   
    for(i=1;i<=n;i++)   
        for(j=1;j<=n;j++)   
             if (graph[i][j] > graph[i][2]+e[2][j])  
                 graph[i][j]=graph[i][2]+graph[2][j];

所以依次类推，只需要在最外层循环中，不断的增加可以中转的城市即可：

//多源最短路径 floyd算法（c/c++）
    void floyd(int graph[][5],int points_num) {
            for(int k=1;k<=points_num;k++)   
                for(int i=1;i<=points_num;i++)   
                     for(int j=1;j<=points_num;j++)   
                         if(graph[i][j]>graph[i][k]+graph[k][j])   
                              graph[i][j]=graph[i][k]+graph[k][j]; 
    }

## 完整测试代码 ##

注意矩阵从（1,1）元素开始

## 算法定义 ##

define INF 999999   //定义无穷大值
    #define POINTS 100    //定义城市数（顶点数）
    #define EDGES 100     //定义航线数（路径数）
    
    //创建图
    void createGraph(int graph[][POINTS]) {
        int mid_tmp,
            points_num,
            edges_num;
        //获取点数 & 边数
        cout<<"请输城市数量，航线数量"<<endl;
        scanf("%d %d",&points_num,&edges_num);
    
        //全部初始化为正无穷
        for (int i = 1;i <= points_num;++i)
            for (int j = 1;j <= points_num;++j) {
                    if (i == j)
                        graph[i][j] = 0;
                    else
                        graph[i][j] = INF;
            }
    
        cout<<"请输入各城市间的航线 ，票价"<<endl;
        //输入边
        int m,n,length;
        for (int i = 1;i <= edges_num;++i) {
            scanf("%d %d %d",&m,&n,&length);
            graph[m][n] = length;
        }
    }
    
    //多源最短路径 floyd算法
    void floyd(int graph[][POINTS],int points_num) {
        for(int k=1;k<=points_num;k++)   
            for(int i=1;i<=points_num;i++)   
                for(int j=1;j<=points_num;j++)   
                    if(graph[i][j]>graph[i][k]+graph[k][j])   
                        graph[i][j]=graph[i][k]+graph[k][j];
    }
    
    //输出最终的结果  
    void showGraph(int graph[][POINTS],int n) {
    
        for(int i=1;i<=n;i++){    
            for(int j=1;j<=n;j++) {   
                printf("%10d",graph[i][j]);   
            }   
            printf("\n");   
        }
    }

## 主函数 ##

int main(void) {
        int graph[POINTS][POINTS];
        createGraph(graph);
        floyd(graph,4);
    
        cout<<"任意城市最低票价图："<<endl;
        showGraph(graph,4);
        system("pause");
    
        return 0;
    }

## 运行截图 ##

![这里写图片描述][70 3]

转载自：[https://blog.csdn.net/lhj884/article/details/47304481][https_blog.csdn.net_lhj884_article_details_47304481]

[70]: /images/20220521/2d9293ec689747069eb83b7b7aaa62a8.png
[70 1]: /images/20220521/8bd85f18f28744d190bd511d70b89ed5.png
[70 2]: /images/20220521/b2eb10a7b7164597a41a415190c95659.png
[70 3]: /images/20220521/a19c9341b53c4cce936a1ea24ce19122.png
[https_blog.csdn.net_lhj884_article_details_47304481]: https://blog.csdn.net/lhj884/article/details/47304481