[ 資料結構 小學堂 ] 圖形結構 : 圖形最短路徑 (頂點兩兩之間的最短距離)

前言 :
由於 Dijkstra 的演算法只能求出某一點到其他頂點的最短距離, 如果要求出圖形中任兩點甚至所有頂點間最短距離, 就必須使用 Floyd 演算法. 該演算法定義可以參考 這裡.

頂點兩兩之間的最短距離 (使用 Floyd 演算法) :
光看 Floyd 演算法相當複雜難懂, 下面將直接以實例說明它的演算法則, 請求出下圖各頂點間的最短路徑 :




範例代碼 :
範例代碼將求下列圖形的頂點間, 兩兩的最短路徑 :
 

view plaincopy to clipboardprint?

1. #include   
2.   
3. using namespace std;  
4. #define SIZE 7  
5. #define NUMBER 6  
6. #define INFINITE 9999 // 無窮大  
7. int Graph_Matrix[SIZE][SIZE];  // 圖形陣列  
8. int distances[SIZE]; // 路徑長度  
9. int distanceMx[SIZE][SIZE] = {INFINITE}; // 路徑長度陣列  
10.   
11. void _BuildGraph_Matrix(int *Path_Cost) {  
12.     int start_Point; // 邊線的起點  
13.     int end_Point; // 邊線的終點  
14.     for(int i=1; i
15.         for(int j=1; j
16.             if(i==j)  
17.                 Graph_Matrix[i][j] = 0; // 對角線為0  
18.             else  
19.                 Graph_Matrix[i][j] = INFINITE;  
20.     // 存入圖形的邊線  
21.     int i=0;  
22.     while(i < SIZE) {  
23.         start_Point = Path_Cost[i*3];  
24.         end_Point = Path_Cost[i*3+1];  
25.         Graph_Matrix[start_Point][end_Point] = Path_Cost[i*3+2];  
26.         i++;  
27.     }  
28. }  
29.   
30. void _PrintGraph_Matrix(){  
31.     for(int i=1; i< SIZE; i++) {  
32.         cout << "Vertx" << i;  
33.         for(int j=1; j
34.             if(Graph_Matrix[i][j] == INFINITE)  
35.                 printf("    x");  
36.             else   
37.                 printf("%5d", Graph_Matrix[i][j]);  
38.         }  
39.         cout << endl;  
40.     }  
41. }  
42.   
43. void _floydShortestPath(int vertex_total) {  
44.     // 圖形長度初始化 (A0 的矩陣)  
45.     for(int i=1; i<=vertex_total; i++) {  
46.         for(int j=i; j<=vertex_total; j++)  {  
47.             distanceMx[i][j] = Graph_Matrix[i][j];  
48.             distanceMx[j][i] = Graph_Matrix[i][j];            
49.         }  
50.     }  
51.     /*John Debug*/  
52.     //for(int i=1; i<=vertex_total; i++) {  
53.     //  for(int j=1; j<=vertex_total; j++)  {  
54.     //      printf("%5d ",distanceMx[i][j]);  
55.     //  }  
56.     //  printf("\n");  
57.     //}  
58.   
59.     // 利用 Floyd 演算法找出所有頂點兩兩間的最短距離  
60.     for(int k=1; k<=vertex_total; k++) // 求出 AK 的矩陣  
61.         for(int i=1; i<=vertex_total; i++)  
62.             for(int j=1; j<=vertex_total; j++)  
63.                 if(distanceMx[i][j] > ( distanceMx[i][k] + distanceMx[k][j]))  
64.                     distanceMx[i][j] = distanceMx[i][k] + distanceMx[k][j];  
65. }  
66.   
67. void main(bool b) {  
68.     int Path_Cost[7][3] = {{1,2,10},  
69.                                                {2,3,20},  
70.                                                {2,4,25},  
71.                                                {3,5,18},  
72.                                                {4,5,22},  
73.                                                {4,6,95},  
74.                                                {5,6,77}};  
75.     _BuildGraph_Matrix(&Path_Cost[0][0]);  
76.     cout << "==========================" << endl;  
77.     cout << "此範例圖形相鄰矩陣如下 :" << endl;  
78.     cout << "==========================" << endl;  
79.     cout << "頂點   vex1 vex2 vex3 vex4 vex5 vex6" << endl;  
80.     _PrintGraph_Matrix();  
81.     cout << "==========================" << endl;  
82.     _floydShortestPath(NUMBER);  
83.     cout << "所有頂點兩兩間最短距離為: " << endl;  
84.     cout << "==========================" << endl;  
85.     cout << "頂點   vex1 vex2 vex3 vex4 vex5 vex6" << endl;  
86.     for(int i=1; i
87.         cout << "Vertx" << i;  
88.         for(int j=1; j
89.             printf("%5d", distanceMx[i][j]);  
90.         }  
91.         cout << endl;  
92.     }  
93. }  

執行結果 :

==========================
此範例圖形相鄰矩陣如下 :
==========================
頂點 vex1 vex2 vex3 vex4 vex5 vex6
Vertx1 0 10 x x x x
Vertx2 x 0 20 25 x x
Vertx3 x x 0 x 18 x
Vertx4 x x x 0 22 95
Vertx5 x x x x 0 77
Vertx6 x x x x x 0
==========================
所有頂點兩兩間最短距離為:
==========================
頂點 vex1 vex2 vex3 vex4 vex5 vex6
Vertx1 0 10 30 35 48 125
Vertx2 10 0 20 25 38 115
Vertx3 30 20 0 40 18 95
Vertx4 35 25 40 0 22 95
Vertx5 48 38 18 22 0 77
Vertx6 125 115 95 95 77 0

補充說明 :
* [ 資料結構 小學堂 ] 圖形結構 : 圖形最短路徑 (單點對全部頂點)