最短路算法-白红宇

最短路算法

阅读量：4364 次

发布时间：2019-06-07

本文共 1752 字，大约阅读时间需要 5 分钟。

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           using namespace std;int map[1000][1000];int main(){ int n,m,i,j,k; cin>>n>>m; for(i=1;i<=n;i++) for(j=1;j<=n;j++) { if(i==j) map[i][j]=0; else map[i][j]=99999999; } for(i=1;i<=m;i++) { int x,y,z; cin>>x>>y>>z; map[x][y]=z; } for(i=1;i<=n;i++) for(j=1;j<=n;j++) for(k=1;k<=n;k++) map[j][k]=min(map[j][k],map[j][i]+map[i][k]); for(i=1;i<=n;i++) { for(j=1;j<=n;j++) { cout<

这是Floyd O(n^3)

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           using namespace std;int map[1000][1000],dis[10000],book[10000];int main(){ int n,m; cin>>n>>m; int i,j,k; for(i=1;i<=n;i++) for(j=1;j<=n;j++) { if(i==j) map[i][j]=0; else map[i][j]=99999999; } while(m--) { int x,y,z; cin>>x>>y>>z; map[x][y]=z; } for(i=1;i<=n;i++) { dis[i]=map[1][i]; } book[1]=1; for(i=1;i<=n;i++) { int u; int minn=99999999; for(j=1;j<=n;j++) { if(dis[j]
           
            dis[u]+map[u][j]) dis[j]=dis[u]+map[u][j]; } } for(i=1;i<=n;i++) { cout<

这是Dijkstra

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           using namespace std;int x[1000],y[1000],z[1000];int dis[1000];int main(){ int n,m; cin>>n>>m; int i,j,k; for(i=1;i<=m;i++) { cin>>x[i]>>y[i]>>z[i]; } for(i=1;i<=n;i++) dis[i]=99999999; dis[1]=0; for(i=1;i<=n-1;i++) { for(j=1;j<=m;j++) { if(dis[y[j]]>dis[x[j]]+z[j]); dis[y[j]]=dis[x[j]]+z[j]; } } for(i=1;i<=n;i++) { cout<