迪克斯屈拉最短路徑算法圖論論(更新版)
【正文】 131109 6 que[ord] = tmp。(adjacent[u][j]infinity_value)) { int newdist=distance_shortest[u]+adjacent[u][j]。amp。//初始值為 0 姓名： 沈敬紅 學院：通信學院 學號： s140131109 5 //開始迭代，迭代 n1 次 for (i=2。//定義存放點的集合 //初始化 for (int i=1。算法結(jié)束時，沿著頂點 Vj 對應(yīng)的 pre_node [j－ 1]追溯，就能確定 V1 到 Vj 最短路 徑，其最短路徑長度等于 distance_shortest [j－ 1]。若加進Vm 做中間結(jié)點，使從 V1 到 Vj 的最短路徑比不加 Vm 的路徑要短，則要修改 Vj 的距離值。在這個圖上，服務(wù)器與服務(wù)器之間的鏈路上都存在著一定的時延，由于網(wǎng)絡(luò)環(huán)境的不同，每個邊上的時延均不相同，有的 只有幾十毫秒，有的卻達到上百毫秒，這些毫秒數(shù)就可以看做邊的權(quán)值，如何選擇最佳的路徑使得服務(wù)器與服務(wù)器之間的數(shù)據(jù)交換所需時間最短的問題，就變成了求解在無向連通加權(quán)圖中尋求最短路徑的問題。 圈：兩端點相同的路（即閉路）稱為圈或回路。當?shù)氐木用裣胫滥芊駨娜我庖魂懙爻霭l(fā)，走遍聯(lián)接該城的 7 座橋又回到原地 ? 其條 件是每座橋都經(jīng)過一次并且只經(jīng)過一次。然后，介紹了迪克斯屈拉（ Dijkstra）最短路徑算法。它以圖為研究對象。按照圖論的表述，在一個圖中，兩點之間的路徑可能有很多條，且每條路徑所經(jīng)過的邊數(shù)可能是不同的，如果是網(wǎng)絡(luò)，每 條路徑的各邊權(quán)數(shù)之和也可能是不同的，怎樣找到一條頂點對頂點之間的各邊權(quán)數(shù)之和為最小的路徑問題稱為最短路問題 [1]。在加權(quán)圖中，鏈（跡、路）的長度為鏈（跡、路）上的所有邊的權(quán)值之和 . 鄰接矩陣：設(shè) G＝ V,E是任意圖，規(guī)定 n 階方陣 A=（ aij）為 G 的鄰接矩陣，其中 aij 為圖 G 中以 xi 為起點且以 yj 為終點的邊的數(shù)目。在這過程中，總保持從 V1 到第一組各頂點的最短路徑都不大于從 V1 到第二組的任何頂點的最短路徑長度。 Dijkstra 算法對問題描述及實現(xiàn)： 六個服務(wù)器節(jié)點 S S S S S5 和 S6，分別如圖表示，各個端點之間的權(quán)值標于節(jié)點間的聯(lián)線之上。 //定義常量 define maxnum 50 //最大節(jié)點數(shù)目 define infinity_value 9999 //無窮大值 //定義數(shù)組，用于存放集合中的數(shù)據(jù) int distance_shortest[maxnum]。//賦值 s[i]=0。 int u=source。 } } s[u]=1。 } } } } } //統(tǒng)計路徑函數(shù) void searchPath(int *pre_node,int source, int destination) { int que[maxnum]。 } que[ord] = source。 // 輸入 p, q 兩端點及其路徑長度 len， num 為要統(tǒng)計的源端點 // 初始化 adjacent[][]為 infinity_value for(int i=1。 cout 請輸入 1 號端點和 2 號端點之間邊的權(quán)值： 20endl。 if (q==0) break。 for( i=1。 Dijkstra(n, num, distance_shortest, pre_node, adjacent)。但是，也可以根據(jù)以上的例子看出，該算法主要特點是以起始點為中心向外層層擴展，直到擴展到終點為
公司管理相關(guān)推薦
鄂ICP備17016276號-1