迪克斯屈拉最短路徑算法圖論論-文庫吧在線文庫
【正文】 works which a lot of severs have to search the shortest path. And then shows the one of shortest path algorithms: The Dijkstra algorithm. Finally, according to the ideas of this algorithm, we put forward a method to achieve the procedure using in the works. Key word Shortest— paths Sever Dijkstra Program 引 言 圖論 (Graph Theory)是數(shù)學(xué)的一個(gè)分支。最后，依據(jù)算法的思想，分別實(shí)現(xiàn)了 Dijkstra 算法在求解計(jì)算網(wǎng)絡(luò)最短路徑的應(yīng)用程序。（具體見“七橋問題”） 在加權(quán)連通圖中，尋求最短路徑的問題有其實(shí)際背景，例如在某一國家或地區(qū)，城市與城市之間都互相連通，從一個(gè)城市到達(dá)另一城市存在著多條路徑，如何實(shí)現(xiàn)最短的路徑完成兩個(gè)城市之間的貨物運(yùn)輸就是一個(gè)解決圖論中實(shí)現(xiàn)最短路徑的問題。 加權(quán)圖：邊上有數(shù)的圖稱為加權(quán)圖（ weighted graph） 。如下圖為網(wǎng)絡(luò)服務(wù)器之間的拓?fù)鋱D： （注： S1S6 為網(wǎng)絡(luò)服務(wù)器節(jié)點(diǎn)，權(quán)值為 10ms/每單位值） 迪克斯屈拉（ Dijkstra）算法實(shí)現(xiàn) Dijkstra 算法 [1]描述： 算法基本思想 ： 一個(gè)頂點(diǎn) V1 作為源點(diǎn)，求該頂點(diǎn)到其他各頂點(diǎn)的最短路徑，迪克斯屈拉 提出了一個(gè)按路徑長度遞增的順序產(chǎn)生最短路徑的方法。修改后再選距離值最小的頂點(diǎn)加入到第一組中。此算法起始頂點(diǎn)也可以不是 V1，起始頂點(diǎn)的序號(hào)由變量 k 給出（即從頂點(diǎn) Vk 出發(fā)）。i=n。i=n。(distance_shortest[j]temp)) { u=j。 if (newdistdistance_shortest[j]) { distance_shortest[j]=newdist。 ord++。 cin n。 cout例如：請(qǐng)輸入端點(diǎn)號(hào)： 1endl。 cout請(qǐng)輸入另一個(gè)端點(diǎn)號(hào)： 。 i=n。 } cout請(qǐng)輸入要統(tǒng)計(jì)的源節(jié)點(diǎn)的端點(diǎn)號(hào)： 。 } } } （ 4）根據(jù)迪克斯屈拉算法得到的程序運(yùn)行最后結(jié)果為： 姓名： 沈敬紅 學(xué)院：通信學(xué)院 學(xué)號(hào)： s140131109 8 圖 圖 （續(xù)） 姓名： 沈敬紅 學(xué)院：通信學(xué)院 學(xué)號(hào)： s140131109 9 從上述實(shí)例中可以看出， Dijkstra 算法是典型的最短路徑路由算法，比較適用于求出圖中 一個(gè)特定頂點(diǎn)到其他各頂點(diǎn)的最短路。由于時(shí)間及個(gè)人學(xué) 習(xí)深度有限，所以在此僅介紹迪克斯屈拉算法的應(yīng)用，其他的最短路徑算法如 Floyd 算法、 Warshall 算法 等將不在敘述，希望本文對(duì)其他學(xué)習(xí)者有一定的幫助。但是，迪克斯屈拉算法無疑仍是一種優(yōu) 秀的算法，可以很好的解決實(shí)際中的最短路徑問題，并且可以和其他算法結(jié)合在一起完成更復(fù)雜的尋路過程。i=n。 ++i) { for(int j=1。 姓名： 沈敬紅 學(xué)院：通信學(xué)院 學(xué)號(hào)： s140131109 7 cinlen。 int judge=1。 ++i) for(int j=1。 i=1。 que[ord] = destination。j=n。 for (int j=1。 } else pre_node[i]=1。 //存放當(dāng)前點(diǎn)的前一
公司管理相關(guān)推薦
鄂ICP備17016276號(hào)-1