欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

图的五种求最短路径算法(Dijkstra、堆优化Dijstra、Bellmon-Ford、SPFA、Floyd-Warshall)

程序员文章站 2022-03-31 08:17:59
图的五种求最短路径算法(Dijkstra、堆优化Dijstra、Bellmon-Ford、SPFA、Floyd-Warshall)V代表顶点个数 E代表边数Dijkstra算法 适合正权(不含负权)稠密图 时间复杂度为O(V^2) 只与顶点个数有关 慎用邻接矩阵 需要考虑初始化为INF 有向图和无向图 重边 和 自环//Acwing 849#includeusing namespace std;const int V=1e3;//最大顶点个数c...
图的五种求最短路径算法(Dijkstra、堆优化Dijstra、Bellmon-Ford、SPFA、Floyd-Warshall)
V代表顶点个数 E代表边数
  1. Dijkstra算法 适合正权(不含负权)稠密图 时间复杂度为O(V^2) 只与顶点个数有关 慎用邻接矩阵 需要考虑初始化为INF 有向图和无向图 重边 和 自环

    //Acwing 849
    #include<iostream>
    using namespace std;
    const int V=1e3;//最大顶点个数
    const int INF = 1e9;
    int adj[V][V]; //邻接矩阵 在存入数据的时候记得考虑初始化,以及无向图和有向图处理方式不同   还要考虑 重边和自环的问题
    bool used[V]; //判断是否使用过
    int d[V]; //最短距离
    int n,m,ts,te; //无向图 给你n个顶点 m条边 求从ts到特最短路径
    int Dijkstra();
    
    int main() {
    	scanf("%d%d%d%d",&n,&m,&ts,&te);
        fill(adj[0],adj[0]+V*V,INF);  //邻接矩阵一定要初始化为INF
        for(int i=0;i<m;i++) {
            int a,b,w;
            scanf("%d%d%d",&a,&b,&w);
            adj[a][b] = adj[b][a] = w;
        }
        int t=Dijkstra();
        if(t==INF) printf("impossible"); //此路不通
        else printf("%d",t); //输出最短路径
    }
    
    int Dijkstra() {
        fill(used,used+V,false); //初始化
        fill(d,d+V,INF);
        d[ts]=0;   //起点最短路径必须设为0
        while(1) {
            int v=-1;
            for(int i=1;i<=n;i++) {  //寻找一个没有使用过的距离起点最近的点
                if(!used[i]&&(v==-1||d[v]>d[i])) v=i;
            }
            if(v==-1) break; //全部都使用过了
            used[v]=true;
            for(int j=1;j<=n;j++) { //更新最短路径
                d[j] = min(d[j],d[v]+adj[v][j]);
            }
        }
        return d[te];
    }
    
  2. 堆优化Dijkstra算法 适合正权稀疏图 时间复杂度O(E logV )

    //Acwing850
    //使用 优先队列 d[V] pair<int,int> 
    #include<iostream>
    #include<queue>
    using namespace std;
    const int INF=1e9,V=1e6;
    int d[V];
    struct edge {int to,cost;};
    vector<edge> G[V];
    typedef pair<int,int> P;
    int n,m;
    int quickDij();
    
    int main() {
    	scanf("%d%d",&n,&m);
        for(int i=1;i<=m;i++) {
            int a,b,w;
            scanf("%d%d%d",&a,&b,&w);
            edge e={b,w}
            G[a].push_back(e);
        }
        int t=quickDij();
        if(t==INF) printf("-1");
        else printf("%d",t);
    }
    
    int quickDij() {
        priority_queue<P,vector<P>,greater<P>> que; //p.first存的是最短距离 p.second存的是顶点
        fill(d,d+V,INF);
        d[1]=0;
        que.push(P(0,1));
        while(que.size()) {
            P p=que.top();
            que.pop();
            int v=p.second;
            if(d[v]<p.first) continue; //冗余了
            for(int i=0;i<G[v].size();i++) {
                edge e=G[v][i];
                if(d[e.to] > d[v] + e.cost) {
                    d[e.to] = d[v]+e.cost;
                    que.push(P(d[e.to],e.to));
                }
            }
        }
        return d[n];
    }
    
  3. Bellmon-Ford算法 适合有负权的图 边数限制的最短路径问题只能用它来求解 时间复杂度 O(V*E)

    //Acwing 853
    //n个顶点让你求从1到n边数不超过k的最短路径
    #include<iostream>
    #include<cstring>
    using namespace std;
    const int INF=1e9,V=600,E=1e6;
    int d[V],backup[V]; //backup用于保留上一次d迭代结果 防止发生串联反应 无法控制边的数量
    int Bellmon();
    int n,m,k;
    struct edge {
        int a,b,w;
    };
    edge es[E]; //存放给的所有边 尽量大
    
    int main() {
        scanf("%d%d%d",&n,&m,&k);
        for(int i=0;i<m;i++) {
            int a,b,w;
            scanf("%d%d%d",&a,&b,&w);
            es[i]={a,b,w};
        }
        int t=Bellmon();
        if(t==INF) printf("impossible");  //或者这句话改为t>INF/2  就可以去掉 下面的if(backup[e.a]!=INF)  就代表没有通路 因为存在负权 有的影响INF  
        else printf("%d",t);
    }
    
    int Bellmon() {
        fill(d,d+V,INF);
        d[1]=0;
        for(int i=0;i<k;i++){
            memcpy(backup,d,sizeof d);
            for(int j=0;j<m;j++) {
                edge e=es[j];
                if(backup[e.a]!=INF) //防止存在负权 对那些明明无法联通的点却改变INF
                	d[e.b] =min(d[e.b],backup[e.a]+e.w); //用上一次迭代结果更新 防止发生串联
            }
        }
        return d[n];
    }
    
  4. SPFA 适合绝大多数情况 但可能被卡样例 存在负圈无法求解 时间复杂度最好是 O(E)

    最坏 O(V*E)

    //Acwing 851
    #include<iostream>
    #include<queue>
    using namespace std;
    const int V=1.5e5,INF=1e9;
    int d[V];
    int nums[V]; //加上这个可以判断负圈
    struct edge {
        int to,cost;
    };
    vector<edge> G[V];
    int SPFA();
    int n,m;
    bool qj[V];
    
    int main() {
        scanf("%d%d",&n,&m);
        for(int i=0;i<m;i++) {
            int a,b,w;
            scanf("%d%d%d",&a,&b,&w);
            edge e={b,w};
            G[a].push_back(e);
        }
        int t=SPFA();
        if(t>INF/2) printf("impossible");
        else printf("%d",t);
    }
    
    int SPFA() {
        fill(qj,qj+V,false);
        fill(d,d+V,INF);
        fill(nums,nums+V,0);
        d[1]=0;
        queue<int> q;
        q.push(1);
        qj[1]=true;
        nums[1]++;
        while(q.size()) {
            int p=q.front();
            q.pop();
            qj[p]=false;
            for(int i=0;i<G[p].size();i++) {
                edge e = G[p][i];
                if(d[e.to]>d[p]+e.cost) {
                    d[e.to] = d[p]+e.cost;
                    if(!qj[e.to]){
                        q.push(e.to);
                        qj[e.to]=true;
                    }
                    nums[e.to]++;
                    if(nums[e.to]>n) return -1; //一个顶点入队超过n次就是图中存在负圈
                }
            }
        }
        return d[n];
    }
    
  5. Floyd-Warshall 多源路径求解 O(V^3)

    int d[MAX_V][MAX_V];  //d是邻接矩阵  循环结束就是i-->j最短路径 V 是顶点个数
    for(int k=0;k<V;k++)
        for(int i=0;i<V;i++)
            for(int j=0;j<v;j++)
                d[i][j] = d[i][k] + d[k][j];
    

本文地址:https://blog.csdn.net/Y810614/article/details/110143980