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

標籤

2010年11月1日 星期一

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

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

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




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

  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

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

沒有留言:

張貼留言

網誌存檔

關於我自己

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