最短路 Hdu-2544

╰半夏微凉° 2022-08-11 16:45 167阅读 0赞

题意很明确，找出1-n的最短距离。

1.dijkstra algorithm

该算法主要思想类似prim algorithm ，但是二者也有细微的差别。其差别请参考：[ZH奶酪][ZH]。

它们都是通过更新一个距离数组来求得答案，都可以用邻接矩阵和邻接表存储距离，而且都要更新完毕n-1个点，它们之间的路也都可以是单向路.....

#include <cstdio>
    #include <cstring>
    #include <iostream>
    #include <algorithm>
    
    using namespace std;
    
    const int inf=0x3f3f3f3f;
    const int N=105;
    
    int dis[N],mat[N][N],vis[N];
    
    int initial(int n){
    	for(int i=0;i<=n;i++)
    		for(int j=0;j<=n;j++)
    			mat[i][j]=inf;
        memset(vis,0,sizeof(vis));
    }
    
    void dijkstra(int n){
        int min=inf,coor=0;vis[1]=1;
        for(int i=2;i<=n;i++)
            {
                dis[i]=mat[1][i];
                if(dis[i]<min){
                    min=dis[i];coor=i;
                }
            }
    			vis[coor]=1;
    			int coun=n-1;
    			while(coun--){
    				min=inf;int tmp=0;
    				for(int i=2;i<=n;i++){
                        if(!vis[i]){
    
                            if(dis[i]>dis[coor]+mat[coor][i]){
                                dis[i]=dis[coor]+mat[coor][i];
    						}
    						if(dis[i]<min){
    							min=dis[i];tmp=i;
                            }
                        }
    				}
    				coor=tmp;
    				vis[coor]=1;
    			}
    }
    
    int main(){
    	int n,m,x,y,val;
    	//freopen("shortest_way.txt","r",stdin);
    	while(scanf("%d%d",&n,&m)==2&&n&&m){
                initial(n);
    		for(int i=0;i<m;i++)
    			{
    				scanf("%d%d%d",&x,&y,&val);
    				mat[x][y]=val;
    				mat[y][x]=val;
    			}
            dijkstra(n);
    		printf("%d\n",dis[n]);
    		}
    		return 0;
    }

2.floyd algorithm

时间复杂度较上一个算法高了一些，但是取而代之的优点是简单易写，代码读起来也十分清楚。其实floyd的代码空间复杂度本是O(|v|^3)但是经过优化就变成了O(|v|^2),其本来的关系式为floyd\[i\]\[j\]\[k\]=min（floyd\[i\]\[j\]\[k-1\],floyd\[i\]\[k\]\[k-1\]+floyd\[k\]\[j\]\[k-1\],优化后为floyd\[i\]\[j\]=floyd\[i\]\[k\]+floyd\[k\]\[j\]这就是常见的floyd的常见关系式。具体的请看：[弗洛伊德算法][Link 1]

#include <cstdio>
    #include <cstring>
    #include <iostream>
    #include <algorithm>
    using namespace std;
    
    const int N=105;
    const int inf=0x3f3f3f3f;
    int floyd[N][N];
    
    int main()
    {
    	int n,m;
    	while(scanf("%d%d",&n,&m)==2&&n&&m)
    	{
    		int x,y,val,i,j;
    		for(i=0;i<=n;i++)
    			for(j=0;j<=n;j++)
    				floyd[i][j]=inf;
    		for(i=0;i<m;i++){
    			scanf("%d%d%d",&x,&y,&val);
    			floyd[x][y]=val;
    			floyd[y][x]=val;
    		}
    		for(int k=1;k<=n;k++)
    			for(i=1;i<=n;i++)
    				for(j=1;j<=n;j++){
    					if(floyd[i][j]>floyd[i][k]+floyd[k][j])
    						floyd[i][j]=floyd[i][k]+floyd[k][j];
    				}
    				printf("%d\n",floyd[1][n]);
    	}
    	return 0;
    }

[ZH]: http://www.cnblogs.com/CheeseZH/archive/2012/10/09/2717106.html
[Link 1]: http://zh.wikipedia.org/wiki/%E5%BC%97%E6%B4%9B%E4%BC%8A%E5%BE%B7%E7%AE%97%E6%B3%95