最短路模板（Dijkstra & Dijkstra算法+堆优化 & bellman_ford & 单源最短路SPFA）

2022-07-11 21:27:07

关于几个的区别和联系：http://www.cnblogs.com/zswbky/p/5432353.html

d.每组的第一行是三个整数T，S和D，表示有T条路，和草儿家相邻的城市的有S个（草儿家到这个城市的距离设为0），草儿想去的地方有D个；

求D个城市中距离草儿家最近的距离。

s.进行1次单源最短路，找出距离最小的即可。

c.Dijkstra单源最短路

/*

Dijkstra单源最短路

权值必须是非负

单源最短路径，Dijkstra算法，邻接矩阵形式，复杂度为O(n^2)

求出源beg到所有点的最短路径，传入图的顶点数，和邻接矩阵cost[][]

返回各点的最短路径lowcost[]，路径pre[].pre[i]记录beg到i路径上的父结点，pre[beg]=-1

可更改路径权类型，但是权值必须为非负

*/

#include<iostream>

#include<stdio.h>

#include<string.h>

using namespace std;

const int MAXN=;

#define typec int

const typec INF=0x3f3f3f3f;//防止后面溢出，这个不能太大

bool vis[MAXN];

int pre[MAXN];

void Dijkstra(typec cost[][MAXN],typec lowcost[],int n,int beg){

    for(int i=;i<n;i++){

        lowcost[i]=INF;vis[i]=false;pre[i]=-;

    }

    lowcost[beg]=;

    for(int j=;j<n;j++){

        int k=-;

        int Min=INF;

        for(int i=;i<n;i++)

            if(!vis[i]&&lowcost[i]<Min){

                Min=lowcost[i];

                k=i;

            }

        if(k==-)break;

        vis[k]=true;

        for(int i=;i<n;i++)

            if(!vis[i]&&lowcost[k]+cost[k][i]<lowcost[i]){

                lowcost[i]=lowcost[k]+cost[k][i];

                pre[i]=k;

            }

    }

}

int cost[MAXN][MAXN];

int lowcost[MAXN];

int main(){

    int T,S,D;

    int a,b,time;

    int city1[MAXN];

    int city2[MAXN];

    while(~scanf("%d%d%d",&T,&S,&D)){

        for(int i=;i<MAXN;++i){

            for(int j=;j<MAXN;++j){

                cost[i][j]=INF;

            }

        }

        memset(vis,false,sizeof(vis));

        for(int i=;i<T;++i){

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

            if(time<cost[a][b]){

                cost[a][b]=time;

                cost[b][a]=time;

            }

        }

        //0作为草儿家

        for(int i=;i<S;++i){

            scanf("%d",&city1[i]);

            cost[][city1[i]]=;

            cost[city1[i]][]=;

        }

        for(int i=;i<D;++i){

            scanf("%d",&city2[i]);

        }

        Dijkstra(cost,lowcost,MAXN,);

        int minTime=lowcost[city2[]];

        for(int i=;i<D;++i){

            if(lowcost[city2[i]]<minTime)

                minTime=lowcost[city2[i]];

        }

        printf("%d\n",minTime);

    }

    return ;

}

c2.Dijkstra算法+堆优化

/*

Dijkstra算法+堆优化

使用优先队列优化，复杂度O(E log E)

使用优先队列优化Dijkstra算法

复杂度O(E log E)

注意对vector<Edge>E[MAXN]进行初始化后加边

*/

#include<iostream>

#include<stdio.h>

#include<vector>

#include<string.h>

#include<queue>

using namespace std;

const int INF=0x3f3f3f3f;

const int MAXN=;

struct qnode{

    int v;

    int c;

    qnode(int _v=,int _c=):v(_v),c(_c){}

    bool operator <(const qnode &r)const{

        return c>r.c;

    }

};

struct Edge{

    int v,cost;

    Edge(int _v=,int _cost=):v(_v),cost(_cost){}

};

vector<Edge>E[MAXN];

bool vis[MAXN];

int dist[MAXN];

//点的编号从1开始

void Dijkstra(int n,int start){

    memset(vis,false,sizeof(vis));

    for(int i=;i<=n;i++)dist[i]=INF;

    priority_queue<qnode>que;

    while(!que.empty())que.pop();

    dist[start]=;

    que.push(qnode(start,));

    qnode tmp;

    while(!que.empty()){

        tmp=que.top();

        que.pop();

        int u=tmp.v;

        if(vis[u])continue;

        vis[u]=true;

        for(int i=;i<E[u].size();i++){

            int v=E[tmp.v][i].v;

            int cost=E[u][i].cost;

            if(!vis[v]&&dist[v]>dist[u]+cost){

                dist[v]=dist[u]+cost;

                que.push(qnode(v,dist[v]));

            }

        }

    }

}

void addedge(int u,int v,int w){

    E[u].push_back(Edge(v,w));

}

int main(){

    int T,S,D;

    int a,b,time;

    int city1[MAXN];

    int city2[MAXN];

    while(~scanf("%d%d%d",&T,&S,&D)){

        for(int i=;i<MAXN;++i){

            E[i].clear();

        }

        for(int i=;i<T;++i){

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

            addedge(a,b,time);//这里有重边了。。没办法，

            addedge(b,a,time);

        }

        //0作为草儿家

        for(int i=;i<S;++i){

            scanf("%d",&city1[i]);

            addedge(,city1[i],);

            addedge(city1[i],,);

        }

        for(int i=;i<D;++i){

            scanf("%d",&city2[i]);

        }

        Dijkstra(MAXN-,);

        int minTime=dist[city2[]];

        for(int i=;i<D;++i){

            if(dist[city2[i]]<minTime)

                minTime=dist[city2[i]];

        }

        printf("%d\n",minTime);

    }

    return ;

}

c3.单源最短路bellman_ford算法

/*

单源最短路bellman_ford算法

单源最短khtkbellman_ford算法，复杂度O(VE)

可以处理负边权图。

可以判断是否存在负环回路。返回true，当且仅当图中不包含从源点可达的负权回路

vector<Edge>E;先E.clear()初始化，然后加入所有边

点的编号从1开始（从0开始简单修改就可以了）

*/

#include<iostream>

#include<stdio.h>

#include<vector>

using namespace std;

const int INF=0x3f3f3f3f;

const int MAXN=;

int dist[MAXN];

struct Edge{

    int u,v;

    int cost;

    Edge(int _u=,int _v=,int _cost=):u(_u),v(_v),cost(_cost){}

};

vector<Edge>E;

//点的编号从1开始

bool bellman_ford(int start,int n){

    for(int i=;i<=n;i++)dist[i]=INF;

    dist[start]=;

    //最多做n-1次

    for(int i=;i<n;i++){

        bool flag=false;

        for(int j=;j<E.size();j++){

            int u=E[j].u;

            int v=E[j].v;

            int cost=E[j].cost;

            if(dist[v]>dist[u]+cost){

                dist[v]=dist[u]+cost;

                flag=true;

            }

        }

        if(!flag)return true;//没有负环回路

    }

    for(int j=;j<E.size();j++)

        if(dist[E[j].v]>dist[E[j].u]+E[j].cost)

            return false;//有负环回路

    return true;//没有负环回路

}

void addedge(int u,int v,int cost){

    E.push_back(Edge(u,v,cost));

}

int main(){

    int T,S,D;

    int a,b,time;

    int city1[MAXN];

    int city2[MAXN];

    while(~scanf("%d%d%d",&T,&S,&D)){

        E.clear();

        for(int i=;i<T;++i){

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

            addedge(a,b,time);//有重边了。

            addedge(b,a,time);

        }

        //0作为草儿家

        for(int i=;i<S;++i){

            scanf("%d",&city1[i]);

            addedge(,city1[i],);

            addedge(city1[i],,);

        }

        for(int i=;i<D;++i){

            scanf("%d",&city2[i]);

        }

        bellman_ford(,MAXN-);//MAXN-1

        int minTime=dist[city2[]];

        for(int i=;i<D;++i){

            if(dist[city2[i]]<minTime)

                minTime=dist[city2[i]];

        }

        printf("%d\n",minTime);

    }

    return ;

}

c4.单源最短路SPFA

/*

单源最短路SPFA

时间复杂度O(kE)

这个是队列实现，有时候改成栈实现会更加快，很容易修改

这个复杂度是不定的

*/

#include<iostream>

#include<stdio.h>

#include<vector>

#include<string.h>

#include<queue>

using namespace std;

const int MAXN=;

const int INF=0x3f3f3f3f;

struct Edge{

    int v;

    int cost;

    Edge(int _v=,int _cost=):v(_v),cost(_cost){}

};

vector<Edge>E[MAXN];

void addedge(int u,int v,int w){

    E[u].push_back(Edge(v,w));

}

bool vis[MAXN];//在队列标志

int cnt[MAXN];//每个点的入队列次数

int dist[MAXN];

bool SPFA(int start,int n){

    memset(vis,false,sizeof(vis));

    for(int i=;i<=n;i++)dist[i]=INF;

    vis[start]=true;

    dist[start]=;

    queue<int>que;

    while(!que.empty())que.pop();

    que.push(start);

    memset(cnt,,sizeof(cnt));

    cnt[start]=;

    while(!que.empty()){

        int u=que.front();

        que.pop();

        vis[u]=false;

        for(int i=;i<E[u].size();i++){

            int v=E[u][i].v;

            if(dist[v]>dist[u]+E[u][i].cost){

                dist[v]=dist[u]+E[u][i].cost;

                if(!vis[v]){

                    vis[v]=true;

                    que.push(v);

                    if(++cnt[v]>n)return false;

                    //cnt[i] 为入队列次数，用来判定是否存在负环回路

                }

            }

        }

    }

    return true;

}

int main(){

    int T,S,D;

    int a,b,time;

    int city1[MAXN];

    int city2[MAXN];

    while(~scanf("%d%d%d",&T,&S,&D)){

        for(int i=;i<MAXN;++i){

            E[i].clear();

        }

        for(int i=;i<T;++i){

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

            addedge(a,b,time);//有重边了。

            addedge(b,a,time);

        }

        //0作为草儿家

        for(int i=;i<S;++i){

            scanf("%d",&city1[i]);

            addedge(,city1[i],);

            addedge(city1[i],,);

        }

        for(int i=;i<D;++i){

            scanf("%d",&city2[i]);

        }

        SPFA(,MAXN-);//MAXN-1

        int minTime=dist[city2[]];

        for(int i=;i<D;++i){

            if(dist[city2[i]]<minTime)

                minTime=dist[city2[i]];

        }

        printf("%d\n",minTime);

    }

    return ;

}

增加一个Floyd的邻接表（这个题不错，有时间看看）

http://blog.163.com/zjut_nizhenyang/blog/static/169570029201111841938607/

Floyd

http://www.cnblogs.com/zswbky/p/5432387.html

上一篇：[ACM_图论] Domino Effect (POJ1135 Dijkstra算法 SSSP 单源最短路算法 中等 模板)


下一篇：bootstrap 菜单之手风琴效果