迪克斯屈拉最短路徑算法圖論論(完整版)
【正文】 個節(jié)點 int adjacent[maxnum][maxnum]。開始時姓名： 沈敬紅 學(xué)院：通信學(xué)院 學(xué)號： s140131109 4 adjacent [i， j]＝ 0 表示頂點 j 未在第一組中，處理中用 s[j]＝ 1 標(biāo)志第 j 個頂點已進(jìn)入第一組。 實現(xiàn)過程描述 ：一開始 第一組 只包括頂點 V1，第二組包括其他所有頂點。若結(jié)點 i 到結(jié)點 j 無邊可連（在有向圖中是方向不一致）時，取 dij＝∞。 姓名： 沈敬紅 學(xué)院：通信學(xué)院 學(xué)號： s140131109 2 圖論相關(guān)概念 [1,2]： 無向圖：每一條邊都是無向邊的圖稱為無向圖。 圖論本身是應(yīng)用數(shù)學(xué)的一部份，因此，歷史上圖論曾經(jīng)被好多位數(shù)學(xué)家各自獨立地建立過。姓名： 沈敬紅 學(xué)院：通信學(xué)院 學(xué)號： s140131109 1 計算機網(wǎng)絡(luò)中迪克斯屈拉 最短路徑 算法 的程序?qū)崿F(xiàn)及應(yīng)用 沈敬紅 S140131109 重慶郵電大學(xué)通信與信息工程學(xué)院 摘要： 本文首先介紹了圖論的發(fā)展歷程，介紹了圖論在實際問題中的應(yīng)用。關(guān)于圖論的文字記載最早出現(xiàn)在歐拉 1736 年的論著中，他所考慮的原始問題有很強的實際背景。 鏈：設(shè) u 和 v 是任意圖 G 的頂點，圖 G 的一條 uv 鏈（ chain 或 walk）是有限的頂點和邊交替的序列 u0e1u1e2… un1enun(u=u0,v=un),其中與邊 e（ 1≤ i≤ n）相鄰的兩個頂點 ui 和 ui1 正好是 ei 的兩個端點。 問題描述 在現(xiàn)有的 Inter 中存在著大量的不同種類的服務(wù)器 [7]，這些服務(wù)器為用戶提供不同種類的數(shù)據(jù)服務(wù)，在服務(wù)器與服務(wù)器之間存在著數(shù)據(jù)的交流。 V1對應(yīng)的距離值為 0，第二組的頂點對應(yīng)的距離值是這樣確定的：若圖中有弧〈 V1，Vj〉，則 Vj 的距離為此弧的權(quán)值，否則 Vj 的距離為 ∞（或用一個很大的數(shù)表示）。 邊的權(quán)值為 adjacent 對應(yīng)的位置的值 ，數(shù)組元素的下標(biāo)等于相關(guān)聯(lián)頂點序號。 //鄰接陣，存放邊值 int n。 } s[source]=1。j=n。j++) { if ((s[j]==0)amp。 ord++。 i) if(i != 1) cout que[i] 。 j=n。 while(judge) { cout請輸入端點號： 。 if (q==0) break。 j=n。i++) { if (i!=num) { cout num號源端點到 i號端點的最短路徑長度值 : distance_shortest[i]。 結(jié)束語 在本文中列舉的網(wǎng)絡(luò)服務(wù)器之間尋找最短路徑的問題比較簡單也比較易理解，通過本算法對實例問題的解決可以更好的幫助理解和掌握迪克斯屈拉算法原理。同時，這個過程中，對 C++編程語言的掌握也給實際問題的解決帶來了方便，這也堅定了我以后動手實踐的信念。 searchPath(pre_node,num, i)。 printf(\n)。// 無向圖 } for( i=1。 if (p==0) break。 //錄入圖的邊權(quán)值 cout請按規(guī)則依次輸入 n個節(jié)點相 鄰的邊數(shù)！ endl。 } void main() { cout請 輸入圖的節(jié)點的個數(shù)： endl。 while(tmp != source) { 姓名： 沈敬紅 學(xué)院：通信學(xué)院 學(xué)號： s140
公司管理相關(guān)推薦
鄂ICP備17016276號-1