迪克斯屈拉最短路徑算法圖論論-資料下載頁
2025-01-07 03:16本頁面
【正文】 lue。 for( i=1。 i=n。 ++i) { for(int j=1。 j=n。 ++j) printf(%8d, adjacent[i][j])。 printf(\n)。 } cout請輸入要統(tǒng)計的源節(jié)點的端點號： 。 cinnum。 Dijkstra(n, num, distance_shortest, pre_node, adjacent)。 // 最短路徑長度 for (i=1。i=n。i++) { if (i!=num) { cout num號源端點到 i號端點的最短路徑長度值 : distance_shortest[i]。 cout ，最短路徑為 : 。 searchPath(pre_node,num, i)。 } } } （ 4）根據(jù)迪克斯屈拉算法得到的程序運行最后結果為： 姓名： 沈敬紅 學院：通信學院 學號： s140131109 8 圖 圖 （續(xù)） 姓名： 沈敬紅 學院：通信學院 學號： s140131109 9 從上述實例中可以看出， Dijkstra 算法是典型的最短路徑路由算法，比較適用于求出圖中 一個特定頂點到其他各頂點的最短路。在實際應用中，需要求出任意兩點之間的最短路，比如選路問題，各個城市之間最短的路線；網(wǎng)絡中路由問題，選擇最短時延路徑等等。但是，也可以根據(jù)以上的例子看出，該算法主要特點是以起始點為中心向外層層擴展，直到擴展到終點為止。對于頂點數(shù)目比較少的圖來說，迪克斯屈拉算法可以比較方便的得出最短路結果，但是，對于頂點數(shù)目比較多的比較復雜的圖來說，運用這種算法將涉及大量的運算，需要反復重復以上的程序，增加運算的時間復雜度，并且遍歷計算的節(jié)點很多，所以效率低。但是，迪克斯屈拉算法無疑仍是一種優(yōu) 秀的算法，可以很好的解決實際中的最短路徑問題，并且可以和其他算法結合在一起完成更復雜的尋路過程。 結束語 在本文中列舉的網(wǎng)絡服務器之間尋找最短路徑的問題比較簡單也比較易理解，通過本算法對實例問題的解決可以更好的幫助理解和掌握迪克斯屈拉算法原理。在這個過程中個人又學到了不少東西，對圖論知識在實際問題中的應用又有了更深入的理解，了解算法的優(yōu)點與缺點，更是鍛煉了動手處理實際問題的思考分析能力。同時，這個過程中，對 C++編程語言的掌握也給實際問題的解決帶來了方便，這也堅定了我以后動手實踐的信念。由于時間及個人學 習深度有限，所以在此僅介紹迪克斯屈拉算法的應用，其他的最短路徑算法如 Floyd 算法、 Warshall 算法 等將不在敘述，希望本文對其他學習者有一定的幫助。 參考文獻 [1].殷劍宏 ,吳開亞 .圖論及其算法 [M].合肥：中國科學技術大學出版社， 2022. [2].卜月華 ,吳建專等 ,圖論及其應用 [M].東南大學出版社 ,2022. [3].左孝玲等 ,離散數(shù)學 [M].上?？茖W技術文獻出版社 ,1999. [4].甘玲 ,邱勁 ,面向對象技術與 Visual C++[M].清華大學出版社 ,2022. [5].Adam Drozdek,陳曙暉 .數(shù)據(jù)結構與算法 C++版 [M].清華大學出版社 ,2022. [6]Paul ,Harvey ,C++程序員教程 [M].電子工業(yè)出版社 ,2022. [7].謝希仁 ,計算機網(wǎng)絡 (第五版 )[M].電子工業(yè)出版社 ,2022. [8].陳樹柏 ,左塏 ,張良震 .網(wǎng)絡圖論及其應用 [M]北京科學出版社 ,1982. [9].劉樹林 ,尹玉妹 .圖的最短路徑算法及網(wǎng)絡中的應用 [J].軟件導刊 ,10(7)
公司管理相關推薦
鄂ICP備17016276號-1