迪克斯屈拉最短路徑算法圖論論(編輯修改稿)
2025-02-03 03:16 本頁面
【文章內(nèi)容簡介】 2）對(duì)上述問題實(shí)現(xiàn)迪克斯屈拉算法的程序過程表述為： 有鄰接矩陣 adjacent表示，若〈 S1， Sj〉是圖中的弧，則 adjacent [i， j]的值等于邊上所帶的權(quán)值，否則adjacent [i， j]等于一個(gè)很大的正數(shù) infinity_value (在 程序中用 9999 表示 )。開始時(shí)姓名： 沈敬紅 學(xué)院：通信學(xué)院 學(xué)號(hào)： s140131109 4 adjacent [i， j]＝ 0 表示頂點(diǎn) j 未在第一組中，處理中用 s[j]＝ 1 標(biāo)志第 j 個(gè)頂點(diǎn)已進(jìn)入第一組。 邊的權(quán)值為 adjacent 對(duì)應(yīng)的位置的值 ，數(shù)組元素的下標(biāo)等于相關(guān)聯(lián)頂點(diǎn)序號(hào)。數(shù)組 distance_shortest [n]的每個(gè)元素為頂點(diǎn)的距離值， pre_node [n]的每個(gè)元素為從 V1 到該頂點(diǎn)的路徑上此頂點(diǎn)的前一個(gè)頂點(diǎn)的序號(hào)，若從 V1 到該頂點(diǎn)無路徑，則用 0 作為其前一個(gè)頂點(diǎn)序號(hào)。算法結(jié)束時(shí)，沿著頂點(diǎn) Vj 對(duì)應(yīng)的 pre_node [j－ 1]追溯，就能確定 V1 到 Vj 最短路 徑，其最短路徑長度等于 distance_shortest [j－ 1]。此算法起始頂點(diǎn)也可以不是 V1，起始頂點(diǎn)的序號(hào)由變量 k 給出（即從頂點(diǎn) Vk 出發(fā)）。源點(diǎn)為 Vk(其中 k 為 1) （ 3）解決上述問題迪克斯屈拉程序源代碼為： include iostream using namespace std。 //定義常量 define maxnum 50 //最大節(jié)點(diǎn)數(shù)目 define infinity_value 9999 //無窮大值 //定義數(shù)組，用于存放集合中的數(shù)據(jù) int distance_shortest[maxnum]。 //存放當(dāng)前節(jié)點(diǎn)到達(dá)源節(jié)點(diǎn)的最短路徑值 int pre_node[maxnum]。 //存放當(dāng)前點(diǎn)的前一個(gè)節(jié)點(diǎn) int adjacent[maxnum][maxnum]。 //鄰接陣，存放邊值 int n。 //節(jié)點(diǎn)個(gè)數(shù) //Dijkstra 算法函數(shù) //n 節(jié)點(diǎn)個(gè)數(shù) ， source 源節(jié)點(diǎn) void Dijkstra(int n,int source,int *distance_shortest,int *pre_node,int adjacent[maxnum][maxnum]) { bool s[maxnum]。//定義存放點(diǎn)的集合 //初始化 for (int i=1。i=n。i++) { distance_shortest[i]=adjacent[source][i]。//賦值 s[i]=0。//將集合置為空 if (distance_shortest[i]==infinity_value) { pre_node[i]=0。 } else pre_node[i]=1。 } s[source]=1。//source 加入集合 distance_shortest[source]=0。//初始值為 0 姓名： 沈敬紅 學(xué)院：通信學(xué)院 學(xué)號(hào)： s140131109 5 //開始迭代，迭代 n1 次 for (i=2。i=n。i++) { int temp=infinity_value。 int u=source。 //找出還未使用的點(diǎn) j 的到源的最小路徑中 distance_shortest[j]。 for (int j=1。j=n。j++) { if ((s[j]==0)amp。amp。(distance_shortest[j]temp)) { u=j。//保存最小
公司管理相關(guān)推薦
鄂ICP備17016276號(hào)-1