本文關鍵詞： 最短路算法 矩陣消去算法 矩陣自定義運算 稀疏網絡 K短路徑算法　出處：《南京郵電大學》2017年碩士論文　論文類型：學位論文

【摘要】：最短路問題作為圖論和復雜網絡中經典問題,現在在日常生活中,也出現在許許多多方面,比如通信網絡,交通網絡,旅行商問題中。然而用來求解最短路徑的問題的解法也是數見不鮮,其中最典型的要數Dijkstra算法、Ford算法和Floyd算法。然而Dijkstra算法只可求出2個指定節(jié)點間的最短距離,Ford算法就只可以求出指定始發(fā)點的最短路徑,而Floyd算法計算過程相當繁瑣。最重要的是,這些算法都是僅僅能解決兩節(jié)點間的1條最短路。而在實際生活中,我們有時還會因為一些給定的前提條件需要求出兩點間次短、漸次短路徑。根據以上的不足,本文提出了基于矩陣運算的最短路徑優(yōu)化算法,主要內容如下:1.針對Ford算法進行改進,提出了一種固定始發(fā)點的矩陣消去算法,通過尋找從一個固定始發(fā)點到其他頂點的路徑,其中包括不經過別的頂點,經過一個頂點、經過兩個頂點等等逐步迭代,找出從固有始發(fā)點到其它的頂點間的最短路。2.給出基于矩陣自定義運算的改良算法。本算法是憑借一種自定義的矩陣運算來求出一個代表每2個節(jié)點間距離的路權修正矩陣,然后用路權修正矩陣和原本的距離矩陣來比較,選擇2個矩陣中相應較小的元素,組成當前的最短路權矩陣,接著,通過有限次迭代,從而獲得各個頂點間的最短路徑。并用MATLAB實現,將這種算法運用到隨機的大規(guī)模復雜網絡中去,從運行時間折線圖上看出這種算法在節(jié)點數到達較大的數量后,算法速度顯著提高,在稀疏網絡中,該算法的效率特別高,這表明該算法的有效性。最終,經過真實的應用場景表明了這種算法的實用性。3.通過對距離矩陣和路徑矩陣的迭代、替換操作,不斷從一個節(jié)點出發(fā)尋找其后繼節(jié)點,同時通過比較路徑長短得到兩點間最短路徑、次短路徑、漸次短路徑,并用一個實際例子對該算法的實用價值加以說明。最后,在一個大型網絡的實際例子中,通過MATLAB對該算法進行仿真,求得指定頂點間最短、次短、漸次短路徑說明該算法能夠在復雜大規(guī)模隨機網絡中得到應用。
[Abstract]:As a classical problem in graph theory and complex network, the shortest path problem appears in many aspects of daily life, such as communication network, transportation network, In the traveling Salesman problem. However, the solution to solve the shortest path problem is not uncommon. The most typical of them are the Dijkstra algorithm and the Floyd algorithm. However, the Dijkstra algorithm can only find the shortest path between the two designated nodes, and only the shortest path of the specified starting point can be obtained by the Dijkstra algorithm. And the Floyd algorithm is rather cumbersome. Most importantly, these algorithms can only solve the shortest path between two nodes. And in real life, we sometimes need to find two points short because of some given preconditions. According to the deficiency above, this paper proposes the shortest path optimization algorithm based on matrix operation. The main contents are as follows: 1. Aiming at the improvement of Ford algorithm, a matrix elimination algorithm with fixed starting point is proposed. By looking for a path from a fixed starting point to another vertex, which includes a step by step iteration through a vertex, a vertex, two vertices, etc. Find out the shortest path from the original point to the other vertices. 2. Give an improved algorithm based on the matrix custom operation. This algorithm is based on a custom matrix operation to find a path weight correction matrix representing the distance between each two nodes. Then the path weight correction matrix is compared with the original distance matrix, and the corresponding smaller elements in the two matrices are selected to form the current shortest path weight matrix. The shortest path between each vertex is obtained, and the algorithm is implemented by MATLAB. The algorithm is applied to random large-scale complex network. From the running time broken line graph, it can be seen that this algorithm has a large number of node points. The efficiency of the algorithm is especially high in sparse networks, which shows the effectiveness of the algorithm. Finally, the practicability of the algorithm is demonstrated by a real application scenario. Finally, by iterating the distance matrix and the path matrix, the algorithm is proved to be practical. Replace operation, constantly from a node to find its successor nodes, and by comparing the length of the path between the shortest path, the second short path, the gradual short path, A practical example is given to illustrate the practical value of the algorithm. Finally, in a practical example of a large network, the algorithm is simulated by MATLAB to obtain the shortest and the second shorter between specified vertices. The gradual short path shows that the algorithm can be applied to complex large scale random networks.
【學位授予單位】：南京郵電大學
【學位級別】：碩士
【學位授予年份】：2017
【分類號】：O157.5

【相似文獻】

相關期刊論文 前10條

1 李幫義,姚恩瑜;最短路網絡及應用[J];系統工程理論與實踐;2000年06期

2 張振坤,王秀梅,范志芬;網絡最短路問題的最優(yōu)解鄰域[J];商丘師范學院學報;2002年02期

3 彭岳林,邱賽兵;網絡最短路靈敏度的算法[J];山東理工大學學報(自然科學版);2004年03期

4 陳志民;;哈明距離下的最短路反問題[J];長春師范學院學報;2007年04期

5 劉海英;;最短路徑問題在管理中的應用[J];福建廣播電視大學學報;2010年04期

6 段冰瀅;;最短路問題的解法探討[J];科協論壇(下半月);2010年11期

7 張振坤;葉希瓊;;網絡最短路的提速問題[J];河南科學;2012年03期

8 李睿;楊子蘭;;限制性最短路問題[J];計算機與信息技術;2012年02期

9 董純飛;劉為國;;一類變權網絡的最短路問題[J];運籌學雜志;1984年01期

10 張?zhí)熹?通過平面上幾個定點的最短路[J];福州大學學報(自然科學版);1986年01期

相關會議論文 前10條

1 袁二明;李瑩;李彪;;基于交通擁堵預測的交通網絡最短路問題的研究[A];“兩型社會”建設與管理創(chuàng)新——第十五屆中國管理科學學術年會論文集（上）[C];2013年

2 施欣;;隨機運輸網絡最短路分布研究[A];復雜巨系統理論·方法·應用——中國系統工程學會第八屆學術年會論文集[C];1994年

3 朱建明;沙丹;;時變網絡中任意等待時間最短路問題的一個對偶算法(英文)[A];第四屆中國智能計算大會論文集[C];2010年

4 俞洋;田亞菲;;一種新的變步長LMS算法及其仿真[A];通信理論與信號處理新進展——2005年通信理論與信號處理年會論文集[C];2005年

5 牛宏睿;李平;史天運;;應急資源調度中最短路邊權不確定性問題的建模與仿真[A];2009年中國智能自動化會議論文集（第七分冊）[南京理工大學學報（增刊）][C];2009年

6 周顥;劉振華;趙保華;;構造型的D~2FA生成算法[A];中國通信學會通信軟件技術委員會2009年學術會議論文集[C];2009年

7 賴桃桃;馮少榮;張東站;;一種基于劃分和密度的快速聚類算法[A];第二十五屆中國數據庫學術會議論文集（一）[C];2008年

8 劉遠新;鄧飛其;羅艷輝;舒添慧;;ERP柔性平臺下物流運輸配送系統算法分析[A];第二十六屆中國控制會議論文集[C];2007年

9 王樹西;白碩;姜吉發(fā);;模式合一的“減首去尾”算法[A];第二屆全國學生計算語言學研討會論文集[C];2004年

10 王萬青;張曉輝;;改進的A~*算法的高效實現[A];2009全國測繪科技信息交流會暨首屆測繪博客征文頒獎論文集[C];2009年

相關重要報紙文章 前1條

1 科文;VIXD算法分析Web異常[N];中國計算機報;2008年

相關博士學位論文 前10條

1 吳六三;基于網絡熵的網絡可靠性研究[D];南京航空航天大學;2014年

2 魏哲學;樣本斷點距離問題的算法與復雜性研究[D];山東大學;2015年

3 劉春明;基于增強學習和車輛動力學的高速公路自主駕駛研究[D];國防科學技術大學;2014年

4 張敏霞;生物地理學優(yōu)化算法及其在應急交通規(guī)劃中的應用研究[D];浙江工業(yè)大學;2015年

5 李紅;流程挖掘算法研究[D];云南大學;2015年

6 卜晨陽;演化約束優(yōu)化及演化動態(tài)優(yōu)化求解算法研究[D];中國科學技術大學;2017年

7 陳拉明;基于非凸優(yōu)化的稀疏重建理論與算法[D];清華大學;2016年

8 劉新旺;多核學習算法研究[D];國防科學技術大學;2013年

9 于濱;城市公交系統模型與算法研究[D];大連理工大學;2006年

10 曾國強;改進的極值優(yōu)化算法及其在組合優(yōu)化問題中的應用研究[D];浙江大學;2011年

相關碩士學位論文 前10條

1 魏翔宇;面向最短路的網絡阻斷問題研究[D];國防科學技術大學;2014年

2 岳曉芳;基于屬性界定的認知診斷Q矩陣估計方法研究[D];華中師范大學;2017年

3 蘇健;自動波方法求解TSP問題[D];西安電子科技大學;2004年

4 雷芬;隨機網絡中的動態(tài)最短路研究[D];中央民族大學;2009年

5 張振抻;網絡最短路的解集結構及有關問題[D];鄭州大學;2002年

6 張美玲;最短路問題的一個改進蟻群算法[D];蘭州大學;2008年

7 黃廈;基于改進蟻群算法的柔性作業(yè)車間調度問題研究[D];昆明理工大學;2015年

8 李平;基于Hadoop的信息爬取與輿情檢測算法研究[D];昆明理工大學;2015年

9 趙官寶;基于位表的關聯規(guī)則挖掘算法研究[D];昆明理工大學;2015年

10 殷文華;移動容遲網絡中基于社會感知的多播分發(fā)算法研究[D];內蒙古大學;2015年

，

本文編號：1547701