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

標籤

2010年10月31日 星期日

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

前言 : 
在一個有向圖形 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]=12D[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]=20D[4]=14. 在其中找出最小頂點D[3] 並加入S集合 : ->D[1], D[4], D[2] 
步驟五 : 
加入最後一個頂點及可得到下表. 
 

範例代碼 : 
  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

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

沒有留言:

張貼留言

網誌存檔

關於我自己

我的相片
Where there is a will, there is a way!