在一個有向圖形 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]
步驟五 :
加入最後一個頂點及可得到下表.
範例代碼 :
- #include
- using namespace std;
- #define SIZE 7
- #define NUMBER 6
- #define INFINITE 9999 // 無窮大
- int Graph_Matrix[SIZE][SIZE]; // 圖形陣列
- int distances[SIZE]; // 路徑長度
- void _BuildGraph_Matrix(int *Path_Cost) {
- int start_Point; // 邊線的起點
- int end_Point; // 邊線的終點
- for(int i=1; i
- for(int j=1; j
- if(i==j)
- Graph_Matrix[i][j] = 0; // 對角線為0
- else
- Graph_Matrix[i][j] = INFINITE;
- // 存入圖形的邊線
- int i=0;
- while(i < SIZE) {
- start_Point = Path_Cost[i*3];
- end_Point = Path_Cost[i*3+1];
- Graph_Matrix[start_Point][end_Point] = Path_Cost[i*3+2];
- i++;
- }
- }
- void _PrintGraph_Matrix(){
- for(int i=1; i< SIZE; i++) {
- cout << "Vertx" << i;
- for(int j=1; j
- if(Graph_Matrix[i][j] == INFINITE)
- printf(" x");
- else
- printf("%5d", Graph_Matrix[i][j]);
- }
- cout << endl;
- }
- }
- void _ShortestPath(int vertex, int vertex_total) {
- int shortest_vertex = 1;// 紀錄最短距離的頂點
- int shortest_distance = -1; // 紀錄最短距離
- int goal[SIZE]; // 用來紀錄該頂點是否被選取
- for(int i=1; i<=vertex_total; i++) {
- goal[i] = 0;
- distances[i] = Graph_Matrix[vertex][i];
- }
- goal[vertex] = 1;
- distances[vertex] = 0;
- cout << endl;
- for(int i=1; i<=(vertex_total-1); i++) {
- shortest_distance = INFINITE;
- // 找最短距離
- for(int j=1; j<=vertex_total; j++) {
- if(goal[j]==0 && shortest_distance > distances[j]) {
- shortest_distance = distances[j];
- shortest_vertex = j;
- }
- }
- goal[shortest_vertex] = 1;
- // 計算頂點到各頂點的最短距離
- for(int j=1; j<=vertex_total; j++) {
- if(goal[j] == 0 && (distances[j] > distances[shortest_vertex] + Graph_Matrix[shortest_vertex][j])) {
- distances[j] = distances[shortest_vertex] + Graph_Matrix[shortest_vertex][j];
- }
- }
- }
- }
- void ch07_07(bool b) {
- //extern int distance[SIZE]; // 宣告為外部變數
- int Path_Cost[7][3] = {{1,2,10},
- {2,3,20},
- {2,4,25},
- {3,5,18},
- {4,5,22},
- {4,6,95},
- {5,6,77}};
- _BuildGraph_Matrix(&Path_Cost[0][0]);
- cout << "==========================" << endl;
- cout << "此範例圖形相鄰矩陣如下 :" << endl;
- cout << "==========================" << endl;
- cout << "頂點 vex1 vex2 vex3 vex4 vex5 vex6" << endl;
- _PrintGraph_Matrix();
- cout << "==========================" << endl;
- _ShortestPath(1, NUMBER); // 找頂點1 到各頂點最短距離
- cout << "頂點1 到各頂點最短距離為: " << endl;
- cout << "==========================" << endl;
- for(int i=1; i
- printf("頂點1 到頂點%2d最短距離=%2d\n", i, distances[i]);
- }
- }
補充說明 :
* [ 資料結構 小學堂 ] 圖形結構 : 圖形最短路徑 (頂點兩兩之間的最短距離)
沒有留言:
張貼留言