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