各种最短路模板

素颜马尾好姑娘i 2022-06-10 04:50 163阅读 0赞

原创 **[http://blog.csdn.net/shuangde800][http_blog.csdn.net_shuangde800]** **， By D\_Double (转载请标明)**

**原创大佬的代码格式不是我喜欢的风格...所以都被我稍作修改了下...**

1. Dijkstra 普通版

#include<stdio.h>
    #include<string.h>
    const int N=105, INF=9999999;
    int d[N], w[N][N],vis[N],n,m;
    void Dijkstra(int src)
    {
    	int i,j,u,tmp;
        for(i=1;i<=n;i++)
        d[i]=INF;
        d[src]=0; 
        memset(vis, 0, sizeof(vis));
        for(i=1;i<=n;i++)
    	{
            u=-1;
            for(j=1;j<=n;j++)
            {
            	if(!vis[j])
    			{
    	            if(u==-1||d[j]<d[u]) 
    				u=j;
            	}
            }			
            vis[u]=1;
            for(j=1;j<=n;j++)
            {
            	if(!vis[j])
    			{
                	tmp=d[u]+w[u][j];
                	if(tmp<d[j]) 
    				d[j] = tmp;
            	}
            }			
        }
    }
    int main()
    {
        int a,b,c,i,j;
        while(scanf("%d%d",&n,&m))
    	{
    		if(n==0&&m==0)break;
            for(i=1;i<=n;i++)
    		{
                w[i][i]=INF;
                for(j=i+1;j<=n;j++)
                w[i][j]=w[j][i]=INF;
            }
            for(i=0;i<m;i++)
    		{
                scanf("%d%d%d",&a,&b,&c);
                w[a][b]=w[b][a]=c;
            }
            Dijkstra(1);
            printf("%d\n",d[n]);
        }
        return 0;
    }

2. Dijkstra+邻接表(用数组实现)+优先队列优化

#include<cstdio>
    #include<cstring>
    #include<utility>
    #include<queue>
    using namespace std;
    const int N=20005;
    const int INF=9999999;
    typedef pair<int,int>pii;
    priority_queue<pii, vector<pii>, greater<pii> >q;
    int d[N], first[N], u[N], v[N], w[N], next[N],n,m;
    bool vis[N];
    // 无向图的输入，注意每输入的一条边要看作是两条边
    void read_graph()
    {
        memset(first,-1,sizeof(first)); //初始化表头
        for(int e=1;e<=m;e++)
    	{
            scanf("%d%d%d",&u[e],&v[e],&w[e]);
            u[e+m]=v[e];
    		v[e+m]=u[e]; 
    		w[e+m]=w[e];  // 增加一条它的反向边       
            next[e]=first[u[e]];  // 插入链表
            first[u[e]]=e;
            next[e+m]=first[u[e+m]]; // 反向边插入链表
            first[u[e+m]]=e+m;
        }
    }
    void Dijkstra(int src)
    {
        memset(vis,0,sizeof(vis));
        for(int i=1;i<=n;i++) 
    	d[i]=INF;
        d[src]=0;
        q.push(make_pair(d[src],src));
        while(!q.empty())
    	{
            pii u=q.top(); 
    		q.pop();
            int x = u.second;
            if(vis[x]) continue;
            vis[x]=true;
            for(int e=first[x];e!=-1;e=next[e])
            {
            	if(d[v[e]]>d[x]+w[e])
    			{
    	            d[v[e]]=d[x]+w[e];
    	            q.push(make_pair(d[v[e]],v[e]));
           	 	} 
            }			
        }
    }
    int main()
    {
        int a,b,c;
        while(scanf("%d%d",&n,&m))
    	{
    		if(n==0&&m==0)break;
            read_graph();
            Dijkstra(1);
            printf("%d\n",d[n]);
        }
        return 0;
    }

3. Dijkstra+邻接表(用vecor实现)+优先队列优化

#include<cstdio>
    #include<cstring>
    #include<utility>
    #include<queue>
    #include<vector>
    using namespace std;
    const int N=105;
    const int INF=9999999;
    typedef pair<int,int>pii;
    vector<pii>G[N];
    priority_queue<pii, vector<pii>, greater<pii> >q;
    int d[N], first[N], u[N], v[N], w[N], next[N],n,m;
    bool vis[N];
    // 无向图的输入，注意没输入的一条边要看作是两条边
    void read_graph()
    {
    	int a,b,c,i;
        for(i=1; i<=n;i++)
        G[i].clear();   
        for(i=1; i<=m;i++)
    	{
            scanf("%d%d%d",&a,&b,&c);
            G[a].push_back(make_pair(b,c));
            G[b].push_back(make_pair(a,c));
        }
    }
    void Dijkstra(int src)
    {
        memset(vis,0,sizeof(vis));
        for(int i=1;i<=n;i++) 
    	d[i]=INF;
        d[src]=0;
        q.push(make_pair(d[src], src));
        while(!q.empty())
    	{
            pii t=q.top(); 
    		q.pop();
            int u=t.second;
            if(vis[u]) continue;
            vis[u]=true;
            for(int v=0;v<G[u].size();v++)
            {
           		if(d[G[u][v].first] > d[u]+G[u][v].second)
    			{
    	            d[G[u][v].first] = d[u]+G[u][v].second;
    	            q.push(make_pair(d[G[u][v].first],G[u][v].first));
    	        }
            }		
        }
    }
    int main()
    {
        int a,b,c;
        while(scanf("%d%d",&n,&m))
    	{
    		if(n==0&&m==0)break;
            read_graph();
            Dijkstra(1);
            printf("%d\n", d[n]);
        }
        return 0;
    }

4.Bellman-Ford算法

#include<cstdio>
    #include<cstring>
    #include<utility>
    #include<queue>
    using namespace std;
    const int N=20005;
    const int INF=9999999;
    int n, m, u[N],v[N],w[N], d[N];
    // 无向图的输入，注意每输入的一条边要看作是两条边
    inline void read_graph()
    {
        for(int e=1;e<=m;e++)
        scanf("%d%d%d",&u[e],&v[e],&w[e]);
    }
    inline void Bellman_Ford(int src)
    {
        for(int i=1;i<=n;i++) 
    	d[i]=INF;
        d[src]=0;
        for(int k=0;k<n-1;k++)
    	{
            for(int i=1;i<=m;i++)
    		{ 
                int x=u[i],y=v[i];
                if(d[x]<INF)
    			{
                    if(d[y]>d[x]+w[i])
                    d[y]=d[x]+w[i];
                }
                if(d[y]<INF)
    			{
                    if(d[x]>d[y]+w[i])
                    d[x]=d[y]+w[i];
                }
            }
        }
    }
    int main()
    {
        int a,b,c;
        while(scanf("%d%d",&n,&m))
    	{
    		if(n==0&&m==0)break;
            read_graph();
            Bellman_Ford(1);
            printf("%d\n", d[n]);
        }
        return 0;
    }

5.SPFA

#include<cstdio>
    #include<cstring>
    #include<utility>
    #include<queue>
    using namespace std;
    const int N=20005;
    const int INF=2147483646>>1;
    int n, m, first[N],next[N],u[N],v[N],w[N], d[N];
    bool vis[N];
    queue<int>q;
    inline void read_graph()
    {
        memset(first, -1, sizeof(first));
        for(int e=1;e<=m;e++)
    	{
            scanf("%d%d%d",&u[e],&v[e],&w[e]);
            u[e+m]=v[e],v[e+m]=u[e],w[e+m]=w[e];
            next[e]=first[u[e]];
            first[u[e]]=e;
            next[e+m]=first[u[e+m]];
            first[u[e+m]]=e+m;
        }
    }
    void SPFA(int src)
    {
        memset(vis,0,sizeof(vis));
        for(int i=1;i<=n;i++)
    	d[i]=INF;
        d[src]=0;
        vis[src]=true;
        q.push(src);
        while(!q.empty())
    	{
            int x = q.front();  
    		q.pop();
            vis[x] = false;
            for(int e=first[x]; e!=-1; e=next[e])
    		{
                if(d[x]+w[e] < d[v[e]])
    			{
                    d[v[e]] = d[x]+w[e];
                    if(!vis[v[e]])
    				{
                        vis[v[e]] = true;
                        q.push(v[e]);
                    }
                }
            }
        } 
    }
    int main()
    {
        int a,b,c;
        while(scanf("%d%d",&n,&m))
    	{
    		if(n==0&&m==0)break;
            read_graph();
            SPFA(1);
            printf("%d\n", d[n]);
        }
        return 0;
    }

6.Floyd算法

#include<cstdio>
    #include<cstring>
    #include<utility>
    #include<queue>
    using namespace std;
    const int N=105;
    const int INF=2147483646;
    int n, m, d[N][N];
    inline void read_graph()
    {
        for(int i=1;i<=n;i++)
    	{
            d[i][i]=INF;
            for(int j=i+1;j<=n;j++)
            d[i][j]=d[j][i]=INF;
        }
        int a,b,c;
        for(int e=1;e<=m;e++)
    	{
            scanf("%d%d%d",&a,&b,&c);
            d[a][b]=d[b][a]=c;
        }
    }
    inline void Floyd(int src)
    {
        for(int k=1;k<=n;k++)
    	{
            for(int i=1;i<=n;i++)
    		{
                for(int j=1;j<=n;j++)
                {
                	if(d[i][k]<INF&&d[k][j]<INF)
                 	d[i][j]=min(d[i][j], d[i][k]+d[k][j]);
                }                
            }
        }
    }
    int main()
    {
        int a,b,c;
        while(scanf("%d%d",&n,&m))
    	{
    		if(n==0&&m==0)break;
            read_graph();
            Floyd(1);
            printf("%d\n", d[1][n]);
        }
        return 0;
    }

[http_blog.csdn.net_shuangde800]: http://blog.csdn.net/shuangde800