Floyd(为了写作业而写）

 1 #include <iostream>
 2 #include <math.h>
 3 #include <vector>
 4 #include <map>
 5 
 6 int MAX=20000;
 7 
 8 using namespace std;
 9 
10 int main()
11 {
12     //                 X   A   B   C   D   E   F   G   H   I   Y
13     int G[12][12] = { {0  ,2  ,MAX,MAX,MAX,MAX,MAX,MAX,MAX,MAX,MAX},
14                       {2  ,0  ,5  ,MAX,3  ,MAX,MAX,MAX,MAX,MAX,MAX},
15                       {MAX,5  ,0  ,MAX,2  ,MAX,MAX,MAX,5  ,MAX,MAX},
16                       {MAX,MAX,MAX,0  ,2  ,MAX,6  ,MAX,MAX,MAX,MAX},
17                       {MAX,3  ,2  ,2  ,0  ,7  ,MAX,MAX,MAX,MAX,MAX},
18                       {MAX,MAX,MAX,MAX,7  ,0  ,MAX,MAX,MAX,MAX,2  },
19                       {MAX,MAX,MAX,6  ,MAX,MAX,0  ,4  ,MAX,MAX,MAX},
20                       {MAX,MAX,MAX,MAX,MAX,MAX,4  ,0  ,MAX,MAX,4  },
21                       {MAX,MAX,5  ,MAX,MAX,MAX,MAX,MAX,0  ,4  ,MAX},
22                       {MAX,MAX,MAX,MAX,MAX,MAX,MAX,MAX,4  ,0  ,MAX},
23                       {MAX,MAX,MAX,MAX,MAX,2  ,MAX,4  ,MAX,MAX,0  } };
24 
25     int D[12][12], path[11][11];
26     for (int i = 0; i < 11; i++)
27     {
28         for (int j = 0; j < 11; j++)
29         {
30             D[i][j] = G[i][j];
31             if (D[i][j] == 0 || D[i][j] == MAX)
32                 path[i][j] = -1;
33             else
34                 path[i][j] = i;
35         }
36     }
37 
38     cout << "初始化D：" << endl;
39     for (int i = 0; i < 11; i++) {
40         for (int j = 0; j < 11; j++)
41             cout << D[i][j] << " ";
42         cout << endl;
43     }
44      
45     cout << "初始化Path：" << endl;
46     for (int i = 0; i < 11; i++) {
47         for (int j = 0; j < 11; j++)
48             cout << path[i][j] << " ";
49         cout << endl;
50     }
51 
52     for (int k = 0; k < 11; k++)
53     {
54         for (int i = 0; i < 11; i++)
55         {
56             for (int j = 0; j < 11; j++)
57             {

58                 if (D[i][j] > D[i][k] + D[k][j])
59                 {
60                     D[i][j] = D[i][k] + D[k][j];
61                     path[i][j] = k;
62                 }
63             }
64         }
65         cout <<"第" <<k<< "次D：" << endl;
66         for (int i = 0; i < 11; i++) {
67             for (int j = 0; j < 11; j++)
68                 cout << D[i][j] << " ";
69             cout << endl;
70         }
71 
72         cout << "第" << k << "次path：" << endl;
73         for (int i = 0; i < 11; i++)
74         {
75             for (int j = 0; j < 11; j++)
76                 cout << path[i][j] << " ";
77             cout << endl;
78         }
79     }
80 }