Skip to content

Dijkstra算法 - 单个节点到所有节点的最短路

Dijkstra算法实现

以下是使用priority_queue优化，以及vector保存邻接表的Dijkstra实现，这个需要背下来。

#include<cstdio>
#include<iostream>
#include<vector>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
struct edge {
    int to,cost;
};
vector<edge> G[10005];
struct d { //记录各种被松弛后的点
    int num,dis;
};
bool operator <(d a,d b) { // priority_queue是大顶堆，重载<以得到小顶堆
    return a.dis > b.dis;
}
int main()
{
    int n, m, s, i, j, k;
    cin >> n >> m >> s;
    for(i=1; i<=m; i++){
        int a,b,c;
        scanf("%d %d %d",&a,&b,&c);
        G[a].push_back(edge{b,c});
    }
    int dis[10005];
    memset(dis, 0x7f, sizeof(dis));
    dis[s]=0;
    priority_queue<d> que;
    que.push(d{s,0});
    while(!que.empty()){
        d e = que.top(); que.pop();
        if (e.dis > dis[e.num])
            continue;
        for(int i=0; i<G[e.num].size(); i++){
            edge eg = G[e.num][i];
            if (dis[eg.to] > dis[e.num]+eg.cost){
                dis[eg.to] = dis[e.num]+eg.cost;
                que.push(d{eg.to, dis[eg.to]});
            }
        }
    }
    for(i=1; i<=n; i++)
        if (dis[i] == dis[10004])
            cout << 2147483647 << ' ';  // 距离无穷大
        else 
            cout << dis[i] << ' ';
    return 0;
}

习题