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

前言 : 
在一個有向圖形 G=(V,E), G 中的每一個邊都有一個比例常數 W(Weight) 與之對應, 如果想求 G 圖形中某一點V0 到其他頂點的最少 W 總和之值, 這類問題就稱為最短路徑問題 (The shortest path problem). 這裡首先討論單點對全部頂點的最短距離. 

單點對全部頂點 : 
一個頂點到多個頂點通常使用 Dijkstra 演算法求得, 有關Dijkstra 的演算法可以參考 這裡, 下面直接來看例子 : 
請找出下圖頂點5 到各頂點的最短路徑 : 
 

做法相當簡單, 首先由頂點5 開始, 找出頂點5 到各頂點間最小距離, 到達不了以 ∞ 表示. 步驟如下 : 
步驟一 : 
 
D[0]= ∞ , D[1]=12, D[2]= ∞ , D[3]=20, D[4]=14. 在其中找出值最小的頂點, 加入S 集合中 : -> D[1] 
步驟二 : 
 
D[0]= ∞ , D[1]=12, D[2]=18 , D[3]=20, D[4]=14. 在其中找出最小的頂點D[4] 並加入S集合中 : ->D[1], D[4] 
步驟三 : 
 
D[0]=26 , D[1]=12, D[2]=18 , D[3]=20, D[4]=14. 在其中找出最小頂點D[2] 並加入S集合 : ->D[1], D[4], D[2] 
步驟四 : 
 
D[0]=26 , D[1]=12, D[2]=18 , D[3]=20, D[4]=14. 在其中找出最小頂點D[3] 並加入S集合 : ->D[1], D[4], D[2] 
步驟五 : 
加入最後一個頂點及可得到下表. 
 

範例代碼 : 

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.   
10. void _BuildGraph_Matrix(int *Path_Cost) {  
11.     int start_Point; // 邊線的起點  
12.     int end_Point; // 邊線的終點  
13.     for(int i=1; i
14.         for(int j=1; j
15.             if(i==j)  
16.                 Graph_Matrix[i][j] = 0; // 對角線為0  
17.             else  
18.                 Graph_Matrix[i][j] = INFINITE;  
19.     // 存入圖形的邊線  
20.     int i=0;  
21.     while(i < SIZE) {  
22.         start_Point = Path_Cost[i*3];  
23.         end_Point = Path_Cost[i*3+1];  
24.         Graph_Matrix[start_Point][end_Point] = Path_Cost[i*3+2];  
25.         i++;  
26.     }  
27. }  
28.   
29. void _PrintGraph_Matrix(){  
30.     for(int i=1; i< SIZE; i++) {  
31.         cout << "Vertx" << i;  
32.         for(int j=1; j
33.             if(Graph_Matrix[i][j] == INFINITE)  
34.                 printf("    x");  
35.             else   
36.                 printf("%5d", Graph_Matrix[i][j]);  
37.         }  
38.         cout << endl;  
39.     }  
40. }  
41.   
42. void _ShortestPath(int vertex, int vertex_total) {  
43.     int shortest_vertex = 1;// 紀錄最短距離的頂點  
44.     int shortest_distance = -1; // 紀錄最短距離  
45.     int goal[SIZE];  // 用來紀錄該頂點是否被選取  
46.     for(int i=1; i<=vertex_total; i++) {  
47.         goal[i] = 0;  
48.         distances[i] = Graph_Matrix[vertex][i];  
49.     }  
50.     goal[vertex] = 1;  
51.     distances[vertex] = 0;  
52.     cout << endl;  
53.     for(int i=1; i<=(vertex_total-1); i++) {  
54.         shortest_distance = INFINITE;  
55.         // 找最短距離  
56.         for(int j=1; j<=vertex_total; j++) {  
57.             if(goal[j]==0 && shortest_distance > distances[j]) {  
58.                 shortest_distance = distances[j];  
59.                 shortest_vertex = j;  
60.             }  
61.         }  
62.         goal[shortest_vertex] = 1;  
63.         // 計算頂點到各頂點的最短距離  
64.         for(int j=1; j<=vertex_total; j++) {  
65.             if(goal[j] == 0 && (distances[j] > distances[shortest_vertex] + Graph_Matrix[shortest_vertex][j])) {  
66.                 distances[j] = distances[shortest_vertex] + Graph_Matrix[shortest_vertex][j];  
67.             }  
68.         }  
69.     }  
70. }  
71.   
72. void ch07_07(bool b) {  
73.     //extern int distance[SIZE]; // 宣告為外部變數  
74.     int Path_Cost[7][3] = {{1,2,10},  
75.                                                {2,3,20},  
76.                                                {2,4,25},  
77.                                                {3,5,18},  
78.                                                {4,5,22},  
79.                                                {4,6,95},  
80.                                                {5,6,77}};  
81.     _BuildGraph_Matrix(&Path_Cost[0][0]);  
82.     cout << "==========================" << endl;  
83.     cout << "此範例圖形相鄰矩陣如下 :" << endl;  
84.     cout << "==========================" << endl;  
85.     cout << "頂點   vex1 vex2 vex3 vex4 vex5 vex6" << endl;  
86.     _PrintGraph_Matrix();  
87.     cout << "==========================" << endl;  
88.     _ShortestPath(1, NUMBER); // 找頂點1 到各頂點最短距離  
89.     cout << "頂點1 到各頂點最短距離為: " << endl;  
90.     cout << "==========================" << endl;  
91.     for(int i=1; i
92.         printf("頂點1 到頂點%2d最短距離=%2d\n", i, distances[i]);  
93.     }  
94. }  

執行結果 : 

==========================
此範例圖形相鄰矩陣如下 :
==========================
頂點 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
==========================

頂點1 到各頂點最短距離為:
==========================
頂點1 到頂點 1最短距離= 0
頂點1 到頂點 2最短距離=10
頂點1 到頂點 3最短距離=30
頂點1 到頂點 4最短距離=35
頂點1 到頂點 5最短距離=48
頂點1 到頂點 6最短距離=125

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