求解单源最短路(Floyd&&Dijstra&&BellmanFord模板)

蔚落 2022-05-19 11:54 142阅读 0赞

读入的时候注意有重边的情况 if(e\[a\]\[b\]>x) e\[a\]\[b\]=e\[b\]\[a\]=x （x是边权，e是邻接矩阵，a、b是边的起点和终点，假设是无向图）

Floyd（不能解决负环）：

void init()
    {
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
            {
                if(i==j) e[i][j]=0;
                else e[i][j]=inf;
            }
    }
    
    void floyd()
    {
        for(int k=1;k<=n;k++)
            for(int i=1;i<=n;i++)
                for(int j=1;j<=n;j++)
                {
                    if(e[i][k]<inf&&e[k][j]<inf)
                        if(e[i][j]>e[i][k]+e[k][j]) e[i][j]=e[i][k]+e[k][j];
                }
    }

Dijkstra（不能解决负权边）：

void init()
    {
        for(int i=0;i<n;i++)
            for(int j=0;j<n;j++)
            {
                if(i==j) e[i][j]=0;
                else e[i][j]=inf;
            }
    }
     
    void dijkstra(int vs)
    {
        int u;
        for(int i=0;i<n;i++)
        {
            vis[i]=0;
            dis[i]=e[vs][i];
        }
        dis[vs]=0;
        for(int i=1;i<n;i++)
        {
            int mmin = inf;
            for(int j=0;j<n;j++)
            {
                if(!vis[j]&&dis[j]<mmin)
                {
                    mmin=dis[j];
                    u=j;
                }
            }
            vis[u]=1;
            for(int j=0;j<n;j++)
            {
                if(!vis[j]&&dis[u]+e[u][j]<dis[j])
                {
                    dis[j]=dis[u]+e[u][j];
                }
            }
        }
    }

Dijkstra（堆优化）：

#include<map>
    #include<set>
    #include<cmath>
    #include<queue>
    #include<stack>
    #include<cstdio>
    #include<vector>
    #include<cctype>
    #include<cstring>
    #include<utility>
    #include<cstdlib>
    #include <iomanip>
    #include<iostream>
    #include<algorithm>
    using namespace std;
    const int maxn = 1e3+7;
    const int inf = 0x3f3f3f3f;
    int n,dis[maxn];
    
    struct node{
        int v,w;
        node(){}
        node(int _v,int _w){v=_v;w=_w;}
        bool operator < (const node &a)const
        {
            if(w==a.w) return v<a.v;
            return w>a.w;
        }
    };
    
    vector<node>edge[maxn];
    
    void dijkstra(int vs)
    {
        for(int i=0;i<=n;i++)
            dis[i]=inf;
        dis[vs]=0;
        priority_queue<node> q;
        while(!q.empty()) q.pop();
        q.push(node(vs,dis[vs]));
        while(!q.empty())
        {
            node x=q.top();q.pop();
            for(int i=0;i<edge[x.v].size();i++)
            {
                node y=edge[x.v][i];
                if(dis[y.v]>x.w+y.w)
                {
                    dis[y.v]=x.w+y.w;
                    q.push(node(y.v,dis[y.v]));
                }
            }
        }
        printf("%d\n",dis[n]);
    }
    
    int main()
    {
        int a,b,c,m;
        while(scanf("%d%d",&n,&m)==2)
        {
            for(int i=0;i<=n;i++)
                edge[i].clear();
            while(m--)
            {
                scanf("%d%d%d",&a,&b,&c);
                edge[a].push_back(node(b,c));
                edge[b].push_back(node(a,c));
            }
            dijkstra(1);
        }
        return 0;
    }

Bellman-Ford（可以解决含负权边的问题）：

/**tot是边的条数,N是点的个数,dis是源点到G中每个点的距离*/
    bool bellman_ford()
    {
        memset(dis,inf,sizeof(dis));
        dis[1]=0;
        bool flag;
        for(int i=1;i<=N-1;i++)
        {
            flag=true;
            for(int j=0;j<tot;j++)
            {
                if(dis[edge[j].v]>dis[edge[j].u]+edge[j].w)
                {
                    dis[edge[j].v]=dis[edge[j].u]+edge[j].w;
                    flag=false;
                }
            }
            if(flag) break;
        }
        for(int i=0;i<tot;i++)
        {
            if(dis[edge[i].v]>dis[edge[i].u]+edge[i].w)
                return true;
        }
        return false;
    }