dijkstra算法（堆优化）

· · 个人记录

算法流程：

dijkstra算法给予贪心的思想，它通过执行以下步骤实现：

  1. 初始化dis[源点]=0,其余节点的dis值为无穷大。
  2. 找一个dis值最小的蓝点x,把节点x标记为已访问。
  3. 遍历xx的所有出边(x,y,z),若dis[y]>dis[x]+z,则令dis[y]=dis[x]+z。
  4. 重复2,3两步,直到所有点都成为白点。

算法结束,dis数组记录了从源点到其它任意点的最短路径。

void dijkstra(int s)
{
    for(int i=1;i<=n;i++) dis[i]=INF;dis[s]=0;
    priority_queue <node> q;
    q.push(node(s,0));
    while(q.size())
    {
        int x=q.top().num;q.pop();
        if(v[x]) continue;
        v[x]=1;
        for(int i=head[x];i;i=net[i])
        {
            int y=ver[i];
            if(!v[y]&&dis[y]>dis[x]+d[i])
            {
                dis[y]=dis[x]+d[i];
                q.push(node(y,dis[y]));
            }
        }
    }
}

时间复杂度O(nlogn)

参考题目：洛谷P4779 【模板】单源最短路径（标准版）

标程：

#include<cstdio>
#include<queue>
const int INF=0x3f3f3f3f;
using namespace std;
int n,m,s,v[100001],dis[100001];
int head[100001],net[200001],ver[200001],d[200001],tot;
struct node
{
    int num,d;
    node (int num, int d) : num(num), d(d) {}
    bool operator <(const node &a) const{return a.d<d;}
};
void add(int x,int y,int z)
{
    ver[++tot]=y;net[tot]=head[x];head[x]=tot;d[tot]=z;
}
void dijkstra(int s)
{
    for(int i=1;i<=n;i++) dis[i]=INF;dis[s]=0;
    priority_queue <node> q;
    q.push(node(s,0));
    while(q.size())
    {
        int x=q.top().num;q.pop();
        if(v[x]) continue;
        v[x]=1;
        for(int i=head[x];i;i=net[i])
        {
            int y=ver[i];
            if(!v[y]&&dis[y]>dis[x]+d[i])
            {
                dis[y]=dis[x]+d[i];
                q.push(node(y,dis[y]));
            }
        }
    }
}
int main()
{
    scanf("%d%d%d",&n,&m,&s);
    while(m--)
    {
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        add(a,b,c);
    }
    dijkstra(s);
    for(int i=1;i<=n;i++) printf("%d ",dis[i]);
    return 0;
}

手写堆版:

#include<cstdio>
const int INF=0x3f3f3f3f;
using namespace std;
int n,m,s,v[100001],dis[100001],cnt;
int head[100001],net[200001],ver[200001],d[200001],tot;
struct node
{
    int num,d;
    bool operator <(const node &a) const{return a.d>d;}
}q[100001];
void add(int x,int y,int z)
{
    ver[++tot]=y;net[tot]=head[x];head[x]=tot;d[tot]=z;
}
void swap(node &a,node &b) {node t=a;a=b;b=t;}
void push(node a)
{
    q[++cnt]=a;
    int now=cnt;
    while(q[now]<q[now/2]&&now) swap(q[now/2],q[now]),now/=2;
}
void pop()
{
    swap(q[1],q[cnt]);cnt--;
    int now=1;
    while(now*2<=cnt)
    {
        int go=now*2;
        if(go<cnt&&q[go+1]<q[go]) go++;
        if(q[go]<q[now])swap(q[go],q[now]);
        else break;
        now=go; 
    }
}
void dijkstra(int s)
{
    for(int i=1;i<=n;i++) dis[i]=INF;dis[s]=0;
    node a={s,0};push(a);
    while(cnt)
    {
        int x=q[1].num;pop();
        if(v[x]) continue;
        v[x]=1;
        for(int i=head[x];i;i=net[i])
        {
            int y=ver[i];
            if(!v[y]&&dis[y]>dis[x]+d[i])
            {
                dis[y]=dis[x]+d[i];
                node yy={y,dis[y]};
                push(yy);
            }
        }
    }
}
int main()
{
    scanf("%d%d%d",&n,&m,&s);
    while(m--)
    {
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        add(a,b,c);
    }
    dijkstra(s);
    for(int i=1;i<=n;i++) printf("%d ",dis[i]);
    return 0;
}