佛洛依德 c++ 最短路径算法

  1 //20142880 唐炳辉 石家庄铁道大学
  2 #include<iostream>
  3 #include<string>
  4 using namespace std;
  5 #define Maxnum 32767
  6 #define N 100
  7 
  8 
  9 
 10 typedef struct
 11 {
 12     string Dianarr[N];                    
 13     string info[N];                    
 14     int arcs[N][N];                
 15     int DianNum,BianNum;
 16 }FloydStruct;
 17 
 18 int LocateVex(FloydStruct G, string a)            
 19 {
 20     int i;
 21     bool flag = 0;
 22     for(i = 0;i < G.DianNum;i++)
 23         if(a == G.Dianarr[i])
 24         {    
 25             flag = 1;
 26             return i;
 27         }
 28     if(flag == 0)
 29     {
 30         return -1;
 31     }
 32 }
 33 void CreateUDN(FloydStruct &G)
 34 {
 35     cout << "请输入顶点数和边数：" << endl;
 36     cin >> G.DianNum >> G.BianNum;
 37     cout << "请输入顶点信息："  << endl;
 38     for(int i = 0;i<G.DianNum;i++)            
 39         cin >> G.Dianarr[i];
 40     for(int i = 0;i<G.DianNum;i++)
 41         for(int j = 0;j<G.DianNum;j++)
 42             G.arcs[i][j] = Maxnum;
 43     string v1,v2;                                
 44     int w,i,j;
 45     cout << "请输入存在路径的两个顶点和路径长度：" << endl;
 46     for(int k = 0;k<G.BianNum;k++)
 47     {
 48         cin >> v1 >> v2 >> w;
 49         i = LocateVex(G,v1);//获取点的数组下标
 50         j = LocateVex(G,v2);
 51         G.arcs[i][j] = w;//权值赋值给两点
 52     }
 53 }
 54 
 55 
 56 int Path[N][N];
 57 int D[N][N];
 58 void Floyd(FloydStruct G)    //佛洛依德                
 59 {
 60     for(int i = 0;i < G.DianNum;i++)
 61         for(int j  = 0; j < G.DianNum;j++)
 62         {
 63             D[i][j] = G.arcs[i][j];
 64             if(D[i][j]<Maxnum)
 65                 Path[i][j] = i;
 66             else 
 67                 Path[i][j] = -1;
 68         }
 69     for(int k = 0;k < G.DianNum;k++)/**核心**/
 70         for(int i  = 0; i < G.DianNum;i++)
 71             for(int j  = 0; j < G.DianNum;j++)
 72                 if(D[i][k] + D[k][j] < D[i][j])
 73                 {
 74                     D[i][j] = D[i][k] + D[k][j];
 75                     Path[i][j] = Path[k][j];
 76                 }
 77 }
 78 
 79 void printFl(FloydStruct G)            //输出                            
 80 {
 81     /*string a,b;
 82     int i,j,font = 1;
 83     cout << "请输入当前位置和要去位置：" << endl;
 84     cin >> a >> b;
 85     //显示最短路径
 86 
 87 
 88     i = LocateVex(G,a);
 89     j = LocateVex(G,b);
 90     if(D[i][j]==Maxnum)
 91          cout << "最短距离为：" << "不可达！"<< endl;
 92     else
 93         cout << "最短距离为：" << D[i][j]<< endl;*/
 94   for(int i=0;i<G.DianNum;i++)
 95     {
 96         for(int j=i+1;j<G.DianNum;j++)
 97         {        
 98                     
 99                     
100 
101             if(D[i][j]!=Maxnum)
102             {int q =0;
103         
104             int j1=j;
105                 int a[20]={100};
106                 while(1)
107                 {
108 
109                     if(Path[i][j1]!=i)
110                     {
111                     
112                         
113                     a[q]=j1=Path[i][j1];
114                     
115                     q=q++;
116                     
117                     
118                     }
119                     else
120                     {
121                     break;}
122                 }
123                 
124                 cout<<G.Dianarr[i]<<"------>";
125                 for(int p=q-1;p>=0;p--)
126                 {
127                     cout<<G.Dianarr[a[p]]<<"------>";
128                 }
129                     cout<<G.Dianarr[j]<< D[i][j]<< endl;
130             }
131         }
132     
133     }
134  //temp终点
135 
136 }
137 
138 void main()
139 {
140     FloydStruct G;
141     CreateUDN(G);//生成邻接矩阵
142     Floyd(G);
143     printFl(G);
144 }