最短路 Hdu-2544-蒲公英云

最短路 Hdu-2544

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

1.dijkstra algorithm

该算法主要思想类似prim algorithm ，但是二者也有细微的差别。其差别请参考：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的常见关系式。具体的请看：弗洛伊德算法

#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;
}