最短路问题

骑猪看日落 2021-10-30 02:48 339阅读 0赞

最短路问题  
有4种算法+广搜  
分为单源最短路和多源最短路

*  floyd算法 多源最短路 O(n^3)
 *  Dijkstra 单源最短路 O
 *  ford算法
 *  johnson算法

优化算法

*  SPFA算法 单源最短路 O(n^2)ford算法的队列优化算法

而最短路问题又有很多种，比如

*  最小环
 *  哈密顿回路
 *  最小生成树

## 弗洛伊德算法Floyd ##

[https://blog.csdn.net/Harington/article/details/81982299][https_blog.csdn.net_Harington_article_details_81982299]

定义g\[i\]\[j\]表示i到j的最短路径，k是中介，i通过k到达j，指的是，只允许经过第k个结点

for(int k=1;k<=n;k++){
        for(int i=1;i<=n;i++){
            if(g[i][k]==INF)continue;//优化时间复杂度
            for(int j=1;j<=n;j++){
                if(g[i][j]>g[i][k]+g[k][j]){
                    g[i][j]=g[i][k]+g[k][j];
                }
            }
        }
    }

时间复杂度是O(n^3),对于大数据不合适，适合与n在100以内的数据

第一行输入结点数n和边数m  
接下来的m行输入无向边情况  
表示u与v相互连接，且距离为d，路费为p  
最后输入a，b，求a到b的最短距离，当距离有多条时，输出路费最小的

## 利用Floyd算法实现多源最短路 ##

本代码没有实现距离多条时，输出路费最小，且n<1000,m<10000;对于O(n^3)时间太慢

#include<iostream>
    #include<cstdio>
    #include<cstring>
    using namespace std;
    const int maxn=1005;
    const int INF=10000000;
    int g[maxn][maxn];
    int mo[maxn][maxn];
    int main(){
        int n,m;
        while(scanf("%d%d",&n,&m)==2&&n&&m){
    
            for(int i=1;i<=n;i++){//初始化
                for(int j=1;j<=n;j++){
                    g[i][j]=INF;
                }
            }
    
            for(int i=0;i<m;i++){
                int u,v,d,p;
                scanf("%d%d%d%d",&u,&v,&d,&p);
                g[u][v]=d;
                g[v][u]=d;
    
                mo[u][v]=p;
                mo[v][u]=p;
            }
    
            for(int k=1;k<=n;k++){
                for(int i=1;i<=n;i++){
                    if(g[i][k]==INF)continue;
                    for(int j=1;j<=n;j++){
                        if(g[k][i]==INF)continue;
                        if(g[i][j]>g[i][k]+g[k][j]){
                            g[i][j]=g[i][k]+g[k][j];
                            mo[i][j]=mo[i][k]+mo[k][j];
                        }
    
                    }
                }
            }
    
            int s,t;
            scanf("%d%d",&s,&t);
            printf("%d %d\n",g[s][t],mo[s][t]);
    
        }
    
        return 0;
    
    }

转载于:https://www.cnblogs.com/Emcikem/p/11342307.html

[https_blog.csdn.net_Harington_article_details_81982299]: https://blog.csdn.net/Harington/article/details/81982299