最短路径算法

古城微笑少年丶 2022-01-07 12:53 578阅读 0赞

1  #include <iostream>
     2  using namespace std;
     3 
     4  const int INF = 100000;
     5  int n=10,path[11][11],dist[11][11],map[11][11];
     6 
     7 /*
     8 函数功能：创建地图城市信息
     9 函数入口参数：空
    10 函数返回值：空
    11 */
    12  void init(){
    13      int i,j;
    14      for(i=1;i<=n;i++)
    15          for(j=1;j<=n;j++)
    16              map[i][j]=(i==j)?0:INF;
    17      map[1][2]=45,map[1][3]=35,map[1][4]=50;
    18      map[2][3]=20,map[2][6]=90,map[2][9]=70;
    19      map[3][5]=50,map[4][5]=50,map[6][7]=20;
    20      map[6][8]=50,map[6][9]=50,map[7][1]=40;
    21      map[7][4]=40,map[10][9]=5;
    22  }
    23  /*
    24 函数功能：Floyd-Warshall算法
    25 函数入口参数：空
    26 函数返回值：空
    27 */
    28  void floyd(){
    29      int i,j,k;
    30      for(i=1;i<=n;i++)
    31          for(j=1;j<=n;j++)
    32              dist[i][j]=map[i][j],path[i][j]=0;
    33      for(k=1;k<=n;k++)
    34          for(i=1;i<=n;i++)
    35              for(j=1;j<=n;j++)
    36                  if(dist[i][k]+dist[k][j]<dist[i][j])
    37                      dist[i][j]=dist[i][k]+dist[k][j],path[i][j]=k;
    38  }
    39   /*
    40 函数功能：输出途径的城市
    41 函数入口参数：空
    42 函数返回值：空
    43 */
    44 
    45  void output(int i,int j){
    46      if(i==j)
    47         return;
    48      if(path[i][j]==0)
    49      {      if(j-1==0)cout<<"00 郑州"<<endl;
    50             else if(j-1==1)cout<<"01 北京"<<endl;
    51             else if(j-1==2)cout<<"02 天津"<<endl;
    52             else if(j-1==3)cout<<"03 南昌"<<endl;
    53             else if(j-1==4)cout<<"04 上海"<<endl;
    54             else if(j-1==5)cout<<"05 贵阳"<<endl;
    55             else if(j-1==6)cout<<"06 株洲"<<endl;
    56             else if(j-1==7)cout<<"07 广州"<<endl;
    57             else if(j-1==8)cout<<"08 兰州"<<endl;
    58             else if(j-1==9)cout<<"09 西宁"<<endl;
    59 
    60      }
    61      else{
    62          output(i,path[i][j]);
    63          output(path[i][j],j);
    64      }
    65  }
    66  int main()
    67  {
    68      int u,v;
    69      init();
    70      floyd();
    71      while(cout<<"请输入俩个城市的编号:")
    72     {
    73          cin>>u>>v;
    74          if(dist[u+1][v+1]==INF)
    75            cout<<"这俩个城市的距离为无穷大"<<endl;
    76          else{
    77             cout<<"途径的城市有:"<<endl;
    78             if(u==0)cout<<"00 郑州"<<endl;
    79             else if(u==1)cout<<"01 北京"<<endl;
    80             else if(u==2)cout<<"02 天津"<<endl;
    81             else if(u==3)cout<<"03 南昌"<<endl;
    82             else if(u==4)cout<<"04 上海"<<endl;
    83             else if(u==5)cout<<"05 贵阳"<<endl;
    84             else if(u==6)cout<<"06 株洲"<<endl;
    85             else if(u==7)cout<<"07 广州"<<endl;
    86             else if(u==8)cout<<"08 兰州"<<endl;
    87             else if(u==9)cout<<"09 西宁"<<endl;
    88             output(u+1,v+1);
    89             cout<<endl;
    90          }
    91          cout<<"这俩个城市的最短距离为："<<dist[u+1][v+1]<<endl;
    92          cout<<endl;
    93      }
    94      return 0;
    95  }

转载于:https://www.cnblogs.com/qisong178878915/p/3428719.html