最短路模板【bellman-ford,dijkstra,floyd-warshall】

Bellman-ford:

/*

bellman ford

*/

#include <iostream>

#include <cstdio>

#include <cstring>

using namespace std;

const int INF = 0x3f3f3f3f;

const int Max = 9999;

typedef struct edge{

    int from,to;

    int ed;

}Edge;

Edge edge[100];

int v[Max];

int d[Max];

int V,E;

void bellman_ford(int s)

{

    memset(d,0x3f,sizeof(d));

    d[s]=0;

    while(true){//如果不存在负圈，最多执行|V|-1次

        bool update = false;

        for(int i=0;i<E;i++){

            Edge e = edge[i];

            if(d[e.from]!=INF&&d[e.to]>d[e.from]+e.ed){

                d[e.to]=d[e.from]+e.ed;

                update = true;

            }

        }

        if(!update) break;

    }

}

bool find_negative_loop()

{

    memset(d,0,sizeof(d));

    for(int i=0;i<V;i++)

        for(int j=0;j<E;j++){

            Edge e = edge[j];

            if(d[e.to]>d[e.from]+e.ed){

                d[e.to] = d[e.from]+e.ed;

                if(i==V-1) return true;

            }

        }

    return false;

}

int main()

{

    int s,e;

    scanf("%d%d",&V,&E);

    for(int i=0;i<V;i++)

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

    for(int i=0;i<E;i++)

        scanf("%d%d%d",&edge[i].from,&edge[i].to,&edge[i].ed);

    if(find_negative_loop()) printf("yes\n");

    else printf("no\n");

    return 0;

}

floyd-warshall：

/*

floyd-warshall

*/

#include <iostream>

#include <cstdio>

#include <cstring>

using namespace std;

const int INF = 0x3f3f3f3f;

const int Max = 200;

int d[Max][Max];

int V,E;

bool floyd_warshall()

{

    for(int k=1;k<=V;k++){

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

            for(int j=1;j<=V;j++){

                d[i][j]=min(d[i][j],d[i][k]+d[k][j]);

            }

        }

    }

    for(int i=1;i<=V;i++)

    if(d[i][i]<0){

        return false;

    }

    return true;

}

int main()

{

    freopen("input.txt","r",stdin);

    scanf("%d%d",&V,&E);

    for(int i=1;i<=V;i++)

        for(int j=1;j<=V;j++)

            d[i][j]=d[j][i] = (i==j?0:INF);

    for(int i=0;i<E;i++)

    {

        int from,to,cost;

        scanf("%d%d%d",&from,&to,&cost);

        d[from][to]=d[to][from]=cost;

    }

    if(floyd_warshall()) printf("%d\n",d[1][V]);

    else printf("负圈\n");

    return 0;

}

dijkstra:

邻接矩阵实现

/*

dijkstra1

*/

#include <iostream>

#include <cstring>

#include <cstdio>

using namespace std;

const int Max = 200;

const int INF = 0x3f3f3f3f;

int d[Max];

int vis[Max];

int cost[Max][Max];

int V,E;

void dijkstra(int s)

{

    memset(d,0x3f,sizeof(d));

    memset(vis,0,sizeof(vis));

    d[s]=0;

    while(1){

        int v = -1;

        for(int u=1;u<=V;u++){

            if(!vis[u]&&(v==-1||d[u]<d[v]))

                v = u;

        }

        if(v==-1) break;

        vis[v]=1;

        for(int u=1;u<=V;u++){

            d[u]=min(d[u],d[v]+cost[v][u]);

        }

    }

}

int main()

{

    //freopen("input.txt","r",stdin);

    int from,to,co;

    cin>>V>>E;

    for(int i=1;i<=V;i++)

        for(int j=1;j<=V;j++)

        cost[i][j]=INF;

    for(int i=0;i<E;i++)

    {

        cin>>from>>to;

        cin>>cost[from][to];

    }

    int s,en;

    cin>>s>>en;

    dijkstra(s);

    cout<<d[en]<<endl;

    return 0;

}

void dijkstra()

{

    memset(dis,0x3f,sizeof(dis));

    memset(vis,0,sizeof(vis));

    dis[1]=0;

    for(int i=1;i<=V;i++)

    {

        int mi = INF,k;

        for(int j=1;j<=V;j++){

            if(vis[j]==0&&dis[j]<mi){

                mi = dis[j];

                k = j;

            }

        }//找最小

        vis[k]=1;

        for(int j=1;j<=V;j++)

            dis[j]=min(dis[j],dis[k]+mp[k][j]);

    }

}

优先队列实现：

/*

dijkstra2

*/

#include <iostream>

#include <cstdio>

#include <vector>

#include <queue>

#include <cstring>

using namespace std;

const int INF = 0x3f3f3f3f;

const int Max = 200;

typedef pair<int,int> P;

typedef struct Edge{

    int v,cost;

};

Edge edge[Max];

vector<Edge> G[Max];

int d[Max];

int V,E;

void dijkstra(int s)

{

    memset(d,0x3f,sizeof(d));

    d[s]=0;

    priority_queue<P ,vector<P>,greater<P> > que;

    que.push(P(0,s));

    while(!que.empty()){

        P top = que.top();que.pop();

        int u = top.second;

        if(d[u]<top.first) continue;

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

            Edge e = G[u][i];

            if(d[e.v]>d[u]+e.cost){

                d[e.v]=d[u]+e.cost;

                que.push(P(d[e.v],e.v));

            }

        }

    }

}

int main()

{

    cin>>V>>E;

    for(int i=0;i<E;i++){

        int u;

        cin>>u>>edge[i].v>>edge[i].cost;

        G[u].push_back(edge[i]);

    }

    int s,e;

    cin>>s>>e;

    dijkstra(s);

    printf("s->e:%d\n",d[e]);

    return 0;

}

路径还原：

            memset(pre,-1,sizeof(pre));

        …………………………

            pre[v]=now;

        …………………………

            vector<int> path;

            int tmp = t;

            while(tmp!=-1){

                path.push_back(tmp);

                tmp = pre[tmp];

            }

            for(int i=path.size()-1;i>=0;i--)

                if(i==0) printf("%d ",path[i]);

                else printf("%d -> ",path[i]);

巴特西

最短路模板【bellman-ford,dijkstra,floyd-warshall】

最新文章

热门文章

巴特西

最短路 模板 【bellman-ford,dijkstra,floyd-warshall】

最新文章

热门文章

最短路模板【bellman-ford,dijkstra,floyd-warshall】