对于dijkstra最短路算法的复习

好久没有看图论了，就从最短路算法开始了。

dijkstra算法的本质是贪心。只适用于不含负权的图中。因为出现负权的话，贪心会出错。

一般来说，我们用堆（优先队列）来优化，将它O（n²）的复杂度优化为O（（m+n）logn）

套用dijkstra模板即可。给出范例：

#include<cstdio>

#include<iostream>

#include<queue>

using namespace std;

int n,m,s,tot,head[500000];

struct edge{

    int next,to,dis;

}e[500000];

inline void add(int x,int y,int w){

    e[++tot].to=y;

    e[tot].next=head[x];

    e[tot].dis=w;

    head[x]=tot;

}

int dis[300000];

bool vis[300000];

struct node{

    int dis,pos;

    bool operator <(const node&x)const{

        return x.dis<dis;

    }

};

priority_queue<node>q;

inline void dijkstra(){

    dis[s]=0;

    q.push((node){0,s});

    while(!q.empty()){

        node tmp=q.top();

        q.pop();

        int x=tmp.pos,d=tmp.dis;

        if(vis[x])continue;

        vis[x]=1;

        for(int i=head[x];i;i=e[i].next){

            int y=e[i].to;

            if(dis[y]>dis[x]+e[i].dis){

                dis[y]=dis[x]+e[i].dis;

                if(!vis[y])q.push((node){dis[y],y});

            }

        }

    }

}

int main(){

    scanf("%d%d%d",&n,&m,&s);

    for(int i=1;i<=n;++i)dis[i]=2147483647;

    for(int i=1;i<=m;++i){

        register int u,v,w;

        scanf("%d%d%d",&u,&v,&w);

        add(u,v,w);

    }

    dijkstra();

    for(int i=1;i<=n;++i)printf("%d ",dis[i]);

    return 0;

}

简单例题1:

仍旧是简单的dijkstra，求某一个点到任何一个点的最短路。

代码：

#include<cstdio>

#include<iostream>

#include<queue>

using namespace std;

int n,m,a,b,c,Ts,Te;

struct edge{

    int next,to,dis;

}e[500000];

struct node{

    int dis,pos;

    bool operator <(const node&x)const{

        return x.dis<dis;

    }

};

int vis[50000],dis[50000];

int head[50000],tot;

priority_queue<node>q;

inline void add(int x,int y,int w){

    e[++tot].to=y;

    e[tot].next=head[x];

    e[tot].dis=w;

    head[x]=tot;

}

inline void dijkstra(){

    dis[Ts]=0;

    q.push((node){0,Ts});

    while(!q.empty()){

        node tmp=q.top();

        q.pop();

        int x=tmp.pos;

        if(vis[x])continue;

        vis[x]=1;

        for(int i=head[x];i;i=e[i].next){

            int y=e[i].to;

            if(dis[y]>dis[x]+e[i].dis){

                dis[y]=dis[x]+e[i].dis;

                if(!vis[y])q.push((node){dis[y],y});

            }

        }

    }

}

int main(){

    scanf("%d%d%d%d",&n,&m,&Ts,&Te);

    for(int i=1;i<=n;++i)dis[i]=2147483647;

    for(int i=1;i<=m;++i){

        scanf("%d%d%d",&a,&b,&c);

        add(a,b,c);add(b,a,c);

    }

    dijkstra();

    printf("%d\n",dis[Te]);

    return 0;

}

巴特西

对于dijkstra最短路算法的复习

最新文章

热门文章