Dijkstra算法（简单讲解+vector实现代码+优先队列优化）

2021fhm · 2022-10-29 15:27:00 · 个人记录

Dijkstra算法是干什么的？

Dijkstra算法的用处就是求单源最短路。注意是单源（意思是求从一个点出发到其他点的最短路），多源最短路（所有点两两直接的最短路）要用Floyd算法求。

它的原理是什么？

从一个点出发，遍历与之相连的点。再从这些点中路径到达的点出发对连边松弛。

需要注意的是使用这个算法，边权不能为负。

如何实现？

        利用广度搜索。

• 将起始点 dis 设为0。
• 选择当前未标记的点中dis值最小的，并对它的所有连边进行松弛。并标记该点。
• 松弛成功则更新的点入队。
• 重复2,3步，直到队列为空。

#include<bits/stdc++.h>
using namespace std;
#define int long long

struct node
{
    int to,w;
    bool operator <(const node &x)const
    {
        return x.w<w;
    }
};
vector<node>a[200005];
priority_queue<node>q;
int n,m,dis[200005],bj[200005],s;
void dij()
{
    dis[s]=0;
    q.push(node{s,0});
    while(!q.empty())
    {
        node ovo=q.top();
        q.pop();
        int p=ovo.to;
        int l=a[p].size();
        if(bj[p])   continue;
        bj[p]=1;
        for(int j=0;j<l;j++)
        {
            int v=a[p][j].to;
            if(dis[v]>dis[p]+a[p][j].w)
            {
                dis[v]=dis[p]+a[p][j].w;
                if(!bj[v])
                {
                    q.push(node{v,dis[v]});
                }
            }
        }
    }
    return;
}
signed main()
{
    cin>>n>>m>>s;
    for(int i=1;i<=n;i++)   dis[i]=2147483647;
    for(int i=1;i<=m;i++)
    {
        int x,y,l;
        cin>>x>>y>>l;
        node t1;
        t1.to=y,t1.w=l;
        a[x].push_back(t1);
    }
    dij();
    for(int i=1;i<=n;i++)
    {
        cout<<dis[i]<<" ";
    }
}

如有错误求大佬们指出，蒟蒻感激不尽qwq