迪克斯屈拉最短路徑算法圖論論-wenkub.com
2025-01-04 03:16 本頁面
【正文】 由于時間及個人學 習深度有限，所以在此僅介紹迪克斯屈拉算法的應用，其他的最短路徑算法如 Floyd 算法、 Warshall 算法 等將不在敘述，希望本文對其他學習者有一定的幫助。但是，迪克斯屈拉算法無疑仍是一種優(yōu) 秀的算法，可以很好的解決實際中的最短路徑問題，并且可以和其他算法結(jié)合在一起完成更復雜的尋路過程。 } } } （ 4）根據(jù)迪克斯屈拉算法得到的程序運行最后結(jié)果為： 姓名： 沈敬紅 學院：通信學院 學號： s140131109 8 圖 圖 （續(xù)） 姓名： 沈敬紅 學院：通信學院 學號： s140131109 9 從上述實例中可以看出， Dijkstra 算法是典型的最短路徑路由算法，比較適用于求出圖中 一個特定頂點到其他各頂點的最短路。i=n。 } cout請輸入要統(tǒng)計的源節(jié)點的端點號： 。 ++i) { for(int j=1。 i=n。 姓名： 沈敬紅 學院：通信學院 學號： s140131109 7 cinlen。 cout請輸入另一個端點號： 。 int judge=1。 cout例如：請輸入端點號： 1endl。 ++i) for(int j=1。 cin n。 i=1。 ord++。 que[ord] = destination。 if (newdistdistance_shortest[j]) { distance_shortest[j]=newdist。j=n。(distance_shortest[j]temp)) { u=j。 for (int j=1。i=n。 } else pre_node[i]=1。i=n。 //存放當前點的前一個節(jié)點 int adjacent[maxnum][maxnum]。此算法起始頂點也可以不是 V1，起始頂點的序號由變量 k 給出（即從頂點 Vk 出發(fā)）。開始時姓名： 沈敬紅 學院：通信學院 學號： s140131109 4 adjacent [i， j]＝ 0 表示頂點 j 未在第一組中，處理中用 s[j]＝ 1 標志第 j 個頂點已進入第一組。修改后再選距離值最小的頂點加入到第一組中。 實現(xiàn)過程描述 ：一開始 第一組 只包括頂點 V1，第二組包括其他所有頂點。如下圖為網(wǎng)絡(luò)服務器之間的拓撲圖： （注： S1S6 為網(wǎng)絡(luò)服務器節(jié)點，權(quán)值為 10ms/每單位值） 迪克斯屈拉（ Dijkstra）算法實現(xiàn) Dijkstra 算法 [1]描述： 算法基本思想 ： 一個頂點 V1 作為源點，求該頂點到其他各頂點的最短路徑，迪克斯屈拉 提出了一個按路徑長度遞增的順序產(chǎn)生最短路徑的方法。若結(jié)點 i 到結(jié)點 j 無邊可連（在有向圖中是方向不一致）時，取 dij＝∞。 加權(quán)圖：邊上有數(shù)的圖稱為加權(quán)圖（ weighted graph） 。 姓名： 沈敬紅 學院：通信學院 學號： s140131109 2 圖論相關(guān)概念 [1,2]： 無向圖：每一條邊都是無向邊的圖稱為無向圖。（具體見“七橋問題”） 在加權(quán)連通圖中，尋求最短路徑的問題有其實際背景，例如在某一國家或地區(qū)，城市與城市之間都互相連通，從一個城市到達另一城市存在著多條路徑，如何實現(xiàn)最短的路徑完成兩個城市之間的貨物運輸就是一個解決圖論中實現(xiàn)最短路徑的問題。 圖論本身是應用數(shù)學的一部份，因此，歷史上圖論曾經(jīng)被好多位數(shù)學家各自獨立地建立過。最后
公司管理相關(guān)推薦
鄂ICP備17016276號-1