迪克斯屈拉最短路徑算法圖論論-文庫吧資料
2025-01-13 03:16本頁面
【正文】 cent[u][j]。j++) { if ((s[j]==0)amp。//加入最短路徑的點(diǎn) //更新 distance_shortest for ( j=1。//保存最小值的號 temp=distance_shortest[j]。amp。j=n。 //找出還未使用的點(diǎn) j 的到源的最小路徑中 distance_shortest[j]。i++) { int temp=infinity_value。//初始值為 0 姓名： 沈敬紅 學(xué)院：通信學(xué)院 學(xué)號： s140131109 5 //開始迭代，迭代 n1 次 for (i=2。 } s[source]=1。//將集合置為空 if (distance_shortest[i]==infinity_value) { pre_node[i]=0。i++) { distance_shortest[i]=adjacent[source][i]。//定義存放點(diǎn)的集合 //初始化 for (int i=1。 //鄰接陣，存放邊值 int n。 //存放當(dāng)前節(jié)點(diǎn)到達(dá)源節(jié)點(diǎn)的最短路徑值 int pre_node[maxnum]。源點(diǎn)為 Vk(其中 k 為 1) （ 3）解決上述問題迪克斯屈拉程序源代碼為： include iostream using namespace std。算法結(jié)束時，沿著頂點(diǎn) Vj 對應(yīng)的 pre_node [j－ 1]追溯，就能確定 V1 到 Vj 最短路 徑，其最短路徑長度等于 distance_shortest [j－ 1]。 邊的權(quán)值為 adjacent 對應(yīng)的位置的值 ，數(shù)組元素的下標(biāo)等于相關(guān)聯(lián)頂點(diǎn)序號。 . G=(V,E) （ 1）此有加權(quán)圖的鄰接矩陣表示為： （ 2）對上述問題實(shí)現(xiàn)迪克斯屈拉算法的程序過程表述為： 有鄰接矩陣 adjacent表示，若〈 S1， Sj〉是圖中的弧，則 adjacent [i， j]的值等于邊上所帶的權(quán)值，否則adjacent [i， j]等于一個很大的正數(shù) infinity_value (在 程序中用 9999 表示 )。如此進(jìn)行下去，直到圖中所有頂點(diǎn)都包括在第一 組中 ，或再也沒有可加入到第一組中的頂點(diǎn)存在為止。若加進(jìn)Vm 做中間結(jié)點(diǎn)，使從 V1 到 Vj 的最短路徑比不加 Vm 的路徑要短，則要修改 Vj 的距離值。 V1對應(yīng)的距離值為 0，第二組的頂點(diǎn)對應(yīng)的距離值是這樣確定的：若圖中有弧〈 V1，Vj〉，則 Vj 的距離為此弧的權(quán)值，否則 Vj 的距離為 ∞（或用一個很大的數(shù)表示）。另外，每個頂點(diǎn)對應(yīng)一個距離值，第一組的頂點(diǎn)對應(yīng)的距離值就是從 V1到此頂點(diǎn)的最短路徑長度，第二組的頂點(diǎn)對應(yīng)的距離值是從 V1 到此頂點(diǎn)的只包括第一組的頂點(diǎn)為中間頂點(diǎn)的最短路徑長度 [2]。此方法的基本姓名： 沈敬紅 學(xué)院：通信學(xué)院 學(xué)號： s140131109 3 思想是：把圖中所有結(jié)點(diǎn)分成兩組，第一組包括已確定最短路徑的頂點(diǎn)，第二組包括尚未確定最短路徑的頂點(diǎn) ，按最短路徑長度遞增的順序逐個把第二組的頂點(diǎn)加到第一組中，直到從 V1 出發(fā)可以到達(dá)的所有頂點(diǎn)都已包括在第一組中。在這個圖上，服務(wù)器與服務(wù)器之間的鏈路上都存在著一定的時延，由于網(wǎng)絡(luò)環(huán)境的不同，每個邊上的時延均不相同，有的 只有幾十毫秒，有的卻達(dá)到上百毫秒，這些毫秒數(shù)就可以看做邊的權(quán)值，如何選擇最佳的路徑使得服務(wù)器與服務(wù)器之間的數(shù)據(jù)交換所需時間最短的問題，就變成了求解在無向連通加權(quán)圖中尋求最短路徑的問題。 問題描述 在現(xiàn)有的 Inter 中存在著大量的不同種類的服務(wù)器 [7]，這些服務(wù)器為用戶提供不同種類的數(shù)據(jù)服務(wù)，在服務(wù)器與服
公司管理相關(guān)推薦
鄂ICP備17016276號-1