迪克斯屈拉最短路徑算法圖論論(存儲(chǔ)版)
【正文】 rd = 1。 for(int i=ord。 i=n。 cout 如果錄入結(jié)束請(qǐng)按 0 結(jié)束 endl。 cout請(qǐng)輸入 p號(hào)端點(diǎn)與 q號(hào)端點(diǎn)之間的權(quán)值： 。 i=n。 // 最短路徑長(zhǎng)度 for (i=1。對(duì)于頂點(diǎn)數(shù)目比較少的圖來(lái)說(shuō)，迪克斯屈拉算法可以比較方便的得出最短路結(jié)果，但是，對(duì)于頂點(diǎn)數(shù)目比較多的比較復(fù)雜的圖來(lái)說(shuō)，運(yùn)用這種算法將涉及大量的運(yùn)算，需要反復(fù)重復(fù)以上的程序，增加運(yùn)算的時(shí)間復(fù)雜度，并且遍歷計(jì)算的節(jié)點(diǎn)很多，所以效率低。 參考文獻(xiàn) [1].殷劍宏 ,吳開(kāi)亞 .圖論及其算法 [M].合肥：中國(guó)科學(xué)技術(shù)大學(xué)出版社， 2022. [2].卜月華 ,吳建專等 ,圖論及其應(yīng)用 [M].東南大學(xué)出版社 ,2022. [3].左孝玲等 ,離散數(shù)學(xué) [M].上?？茖W(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ì)算機(jī)網(wǎng)絡(luò) (第五版 )[M].電子工業(yè)出版社 ,2022. [8].陳樹(shù)柏 ,左塏 ,張良震 .網(wǎng)絡(luò)圖論及其應(yīng)用 [M]北京科學(xué)出版社 ,1982. [9].劉樹(shù)林 ,尹玉妹 .圖的最短路徑算法及網(wǎng)絡(luò)中的應(yīng)用 [J].軟件導(dǎo)刊 ,10(7), 。在實(shí)際應(yīng)用中，需要求出任意兩點(diǎn)之間的最短路，比如選路問(wèn)題，各個(gè)城市之間最短的路線；網(wǎng)絡(luò)中路由問(wèn)題，選擇最短時(shí)延路徑等等。 cinnum。 ++i) distance_shortest[i] = infinity_value。 cin q 。 cout 請(qǐng)輸入另一個(gè)端點(diǎn)號(hào)： 2endl。 int p, q, len,num。 tmp = pre_node[tmp]。 pre_node[j]=u。//保存最小值的號(hào) temp=distance_shortest[j]。i++) { int temp=infinity_value。i++) { distance_shortest[i]=adjacent[source][i]。源點(diǎn)為 Vk(其中 k 為 1) （ 3）解決上述問(wèn)題迪克斯屈拉程序源代碼為： include iostream using namespace std。如此進(jìn)行下去，直到圖中所有頂點(diǎn)都包括在第一 組中 ，或再也沒(méi)有可加入到第一組中的頂點(diǎn)存在為止。此方法的基本姓名： 沈敬紅 學(xué)院：通信學(xué)院 學(xué)號(hào)： s140131109 3 思想是：把圖中所有結(jié)點(diǎn)分成兩組，第一組包括已確定最短路徑的頂點(diǎn)，第二組包括尚未確定最短路徑的頂點(diǎn) ，按最短路徑長(zhǎng)度遞增的順序逐個(gè)把第二組的頂點(diǎn)加到第一組中，直到從 V1 出發(fā)可以到達(dá)的所有頂點(diǎn)都已包括在第一組中。若邊 e 標(biāo)記數(shù)為 k，則稱邊 e 的權(quán) (weight)為 k。同樣，比如需要架設(shè)電網(wǎng)、通信網(wǎng)絡(luò)以及其他的有線網(wǎng)絡(luò)，基于全網(wǎng)的考慮之下，點(diǎn)和點(diǎn)之間怎樣架設(shè)一條最短的線路就是一個(gè)實(shí)際的最短路問(wèn)題。 關(guān)鍵詞： 最短路徑 服務(wù)器 Dijkstra 算法 程序 Abstract in this paper, we firstly introduce the process of theory of graph. secondly, we give the introduction of the problem of shortest path and related content, and the application of
公司管理相關(guān)推薦
鄂ICP備17016276號(hào)-1