迪克斯屈拉最短路徑算法圖論論(文件)
【正文】 ]=1。i++) { int temp=infinity_value。j=n。//保存最小值的號 temp=distance_shortest[j]。j++) { if ((s[j]==0)amp。 pre_node[j]=u。 ord++。 tmp = pre_node[tmp]。 i) if(i != 1) cout que[i] 。 int p, q, len,num。 j=n。 cout 請輸入另一個端點號： 2endl。 while(judge) { cout請輸入端點號： 。 cin q 。 if (q==0) break。 ++i) distance_shortest[i] = infinity_value。 j=n。 cinnum。i++) { if (i!=num) { cout num號源端點到 i號端點的最短路徑長度值 : distance_shortest[i]。在實際應(yīng)用中，需要求出任意兩點之間的最短路，比如選路問題，各個城市之間最短的路線；網(wǎng)絡(luò)中路由問題，選擇最短時延路徑等等。 結(jié)束語 在本文中列舉的網(wǎng)絡(luò)服務(wù)器之間尋找最短路徑的問題比較簡單也比較易理解，通過本算法對實例問題的解決可以更好的幫助理解和掌握迪克斯屈拉算法原理。 參考文獻(xiàn) [1].殷劍宏 ,吳開亞 .圖論及其算法 [M].合肥：中國科學(xué)技術(shù)大學(xué)出版社， 2022. [2].卜月華 ,吳建專等 ,圖論及其應(yīng)用 [M].東南大學(xué)出版社 ,2022. [3].左孝玲等 ,離散數(shù)學(xué) [M].上海科學(xué)技術(shù)文獻(xiàn)出版社 ,1999. [4].甘玲 ,邱勁 ,面向?qū)ο蠹夹g(shù)與 Visual C++[M].清華大學(xué)出版社 ,2022. [5].Adam Drozdek,陳曙暉 .數(shù)據(jù)結(jié)構(gòu)與算法 C++版 [M].清華大學(xué)出版社 ,2022. [6]Paul ,Harvey ,C++程序員教程 [M].電子工業(yè)出版社 ,2022. [7].謝希仁 ,計算機(jī)網(wǎng)絡(luò) (第五版 )[M].電子工業(yè)出版社 ,2022. [8].陳樹柏 ,左塏 ,張良震 .網(wǎng)絡(luò)圖論及其應(yīng)用 [M]北京科學(xué)出版社 ,1982. [9].劉樹林 ,尹玉妹 .圖的最短路徑算法及網(wǎng)絡(luò)中的應(yīng)用 [J].軟件導(dǎo)刊 ,10(7), 。同時，這個過程中，對 C++編程語言的掌握也給實際問題的解決帶來了方便，這也堅定了我以后動手實踐的信念。對于頂點數(shù)目比較少的圖來說，迪克斯屈拉算法可以比較方便的得出最短路結(jié)果，但是，對于頂點數(shù)目比較多的比較復(fù)雜的圖來說，運(yùn)用這種算法將涉及大量的運(yùn)算，需要反復(fù)重復(fù)以上的程序，增加運(yùn)算的時間復(fù)雜度，并且遍歷計算的節(jié)點很多，所以效率低。 searchPath(pre_node,num, i)。 // 最短路徑長度 for (i=1。 printf(\n)。 i=n。// 無向圖 } for( i=1。 cout請輸入 p號端點與 q號端點之間的權(quán)值： 。 if (p==0) break。 cout 如果錄入結(jié)束請按 0 結(jié)束 endl。 //錄入圖的邊權(quán)值 cout請按規(guī)則依次輸入 n個節(jié)點相 鄰的邊數(shù)！ endl。 i=n。 } void main() { cout請 輸入圖的節(jié)點的個數(shù)： endl。 for(int i=ord。 while(tmp != source) { 姓名： 沈敬紅 學(xué)院：通信學(xué)院 學(xué)號： s140131109
公司管理相關(guān)推薦
鄂ICP備17016276號-1