C++

「最短路」Dijkstra算法模版

Dijkstra算法配合不同的存图方式时间复杂度从O(N²) ~ O(NE),加上优先级队列(堆)的优化能降到O((m+n)logn),那么这篇我列举出一些模版代码,仅供参考。但是我还是更喜欢用SPFA…

Dijkstra & 邻接矩阵存图模版:

#include <iostream>
#include <cstdlib>
#include <cstring>
using namespace std;
#define N 105
int map[N][N],vis[N],dis[N];
int n,e,m,s,w;
void addedge(int a,int b,int c){map[a][b]=c;}
void dijkstra(){
    memset(dis,127,sizeof(dis));
    dis[s]=0;
    for(int i=1;i<n;i++){
        m=21000000;
        for(int j=1;j<=n;j++)
            if(dis[j]<m && vis[j]==0)
                m=dis[j],w=j;    //筛选最短出边,这里可以用priority_queue优化
        vis[w]=1;
        for(int j=1;j<=n;j++)
            if(map[w][j]!=0 && vis[j]==0 && dis[j]>dis[w]+map[w][j])
                dis[j]=dis[w]+map[w][j];
    }
}
int main(){
    cin>>n>>e>>s;
    for(int i=1;i<=e;i++){
        int x,y,z;
        cin>>x>>y>>z;
        addedge(x,y,z);
        addedge(y,x,z);
    }
    dijkstra();
    for(int i=1;i<=n;i++) cout<<dis[i]<<endl;
    return 0;
}
/*
测试数据:
5 7 1
1 2 4
1 3 29
3 2 6
2 5 3
3 5 4
4 5 6
1 4 4
*/

优先队列优化版:

#include <iostream>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
#define INF 0xfffffff
#define maxn 1002
struct Node{
    int e;
    int w;
    friend bool operator < (Node A, Node B){return  A.w > B.w;}
};
bool vis[maxn];
int m, n;
vector< vector<Node> > G;
int Dij(int Star,int End){
    Node P, Pn;
    P.e = Star;
    P.w = 0;
    priority_queue<Node> Q;
    Q.push(P);
    while(!Q.empty()){
        P = Q.top();
        Q.pop();
        if( vis[P.e] ) continue;
        vis[P.e] = true;
        if( P.e == End ) return P.w;
        int len = G[P.e].size();
        for(int i=0; i< len; i++){
            Pn.e = G[P.e][i].e;
            Pn.w = G[P.e][i].w + P.w;

            if( !vis[Pn.e] )
                Q.push(Pn);
        }
    }
    return -1;
}
int main(){
    Node P;
    while(cin >> n >> m, m+n){
        G.clear();
        G.resize(n+1);
        memset(vis,false,sizeof(vis));
        for(int i=0; i<m; i++){
            int a, b, c;
            cin >> a >> b >> c;
            P.e = b;
            P.w = c;
            G[a].push_back(P);
            P.e = a;
            G[b].push_back(P);
        }
        int ans = Dij(1,n);
        cout << ans << endl;
    }
    return 0;
}
分享到