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