本文關(guān)鍵詞： 最短路算法 矩陣消去算法 矩陣自定義運(yùn)算 稀疏網(wǎng)絡(luò) K短路徑算法　出處：《南京郵電大學(xué)》2017年碩士論文　論文類型：學(xué)位論文

【摘要】：最短路問(wèn)題作為圖論和復(fù)雜網(wǎng)絡(luò)中經(jīng)典問(wèn)題,現(xiàn)在在日常生活中,也出現(xiàn)在許許多多方面,比如通信網(wǎng)絡(luò),交通網(wǎng)絡(luò),旅行商問(wèn)題中。然而用來(lái)求解最短路徑的問(wèn)題的解法也是數(shù)見(jiàn)不鮮,其中最典型的要數(shù)Dijkstra算法、Ford算法和Floyd算法。然而Dijkstra算法只可求出2個(gè)指定節(jié)點(diǎn)間的最短距離,Ford算法就只可以求出指定始發(fā)點(diǎn)的最短路徑,而Floyd算法計(jì)算過(guò)程相當(dāng)繁瑣。最重要的是,這些算法都是僅僅能解決兩節(jié)點(diǎn)間的1條最短路。而在實(shí)際生活中,我們有時(shí)還會(huì)因?yàn)橐恍┙o定的前提條件需要求出兩點(diǎn)間次短、漸次短路徑。根據(jù)以上的不足,本文提出了基于矩陣運(yùn)算的最短路徑優(yōu)化算法,主要內(nèi)容如下:1.針對(duì)Ford算法進(jìn)行改進(jìn),提出了一種固定始發(fā)點(diǎn)的矩陣消去算法,通過(guò)尋找從一個(gè)固定始發(fā)點(diǎn)到其他頂點(diǎn)的路徑,其中包括不經(jīng)過(guò)別的頂點(diǎn),經(jīng)過(guò)一個(gè)頂點(diǎn)、經(jīng)過(guò)兩個(gè)頂點(diǎn)等等逐步迭代,找出從固有始發(fā)點(diǎn)到其它的頂點(diǎn)間的最短路。2.給出基于矩陣自定義運(yùn)算的改良算法。本算法是憑借一種自定義的矩陣運(yùn)算來(lái)求出一個(gè)代表每2個(gè)節(jié)點(diǎn)間距離的路權(quán)修正矩陣,然后用路權(quán)修正矩陣和原本的距離矩陣來(lái)比較,選擇2個(gè)矩陣中相應(yīng)較小的元素,組成當(dāng)前的最短路權(quán)矩陣,接著,通過(guò)有限次迭代,從而獲得各個(gè)頂點(diǎn)間的最短路徑。并用MATLAB實(shí)現(xiàn),將這種算法運(yùn)用到隨機(jī)的大規(guī)模復(fù)雜網(wǎng)絡(luò)中去,從運(yùn)行時(shí)間折線圖上看出這種算法在節(jié)點(diǎn)數(shù)到達(dá)較大的數(shù)量后,算法速度顯著提高,在稀疏網(wǎng)絡(luò)中,該算法的效率特別高,這表明該算法的有效性。最終,經(jīng)過(guò)真實(shí)的應(yīng)用場(chǎng)景表明了這種算法的實(shí)用性。3.通過(guò)對(duì)距離矩陣和路徑矩陣的迭代、替換操作,不斷從一個(gè)節(jié)點(diǎn)出發(fā)尋找其后繼節(jié)點(diǎn),同時(shí)通過(guò)比較路徑長(zhǎng)短得到兩點(diǎn)間最短路徑、次短路徑、漸次短路徑,并用一個(gè)實(shí)際例子對(duì)該算法的實(shí)用價(jià)值加以說(shuō)明。最后,在一個(gè)大型網(wǎng)絡(luò)的實(shí)際例子中,通過(guò)MATLAB對(duì)該算法進(jìn)行仿真,求得指定頂點(diǎn)間最短、次短、漸次短路徑說(shuō)明該算法能夠在復(fù)雜大規(guī)模隨機(jī)網(wǎng)絡(luò)中得到應(yīng)用。
[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.
【學(xué)位授予單位】：南京郵電大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2017
【分類號(hào)】：O157.5

【相似文獻(xiàn)】

相關(guān)期刊論文 前10條

1 李幫義,姚恩瑜;最短路網(wǎng)絡(luò)及應(yīng)用[J];系統(tǒng)工程理論與實(shí)踐;2000年06期

2 張振坤,王秀梅,范志芬;網(wǎng)絡(luò)最短路問(wèn)題的最優(yōu)解鄰域[J];商丘師范學(xué)院學(xué)報(bào);2002年02期

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

4 陳志民;;哈明距離下的最短路反問(wèn)題[J];長(zhǎng)春師范學(xué)院學(xué)報(bào);2007年04期

5 劉海英;;最短路徑問(wèn)題在管理中的應(yīng)用[J];福建廣播電視大學(xué)學(xué)報(bào);2010年04期

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

7 張振坤;葉希瓊;;網(wǎng)絡(luò)最短路的提速問(wèn)題[J];河南科學(xué);2012年03期

8 李睿;楊子蘭;;限制性最短路問(wèn)題[J];計(jì)算機(jī)與信息技術(shù);2012年02期

9 董純飛;劉為國(guó);;一類變權(quán)網(wǎng)絡(luò)的最短路問(wèn)題[J];運(yùn)籌學(xué)雜志;1984年01期

10 張?zhí)熹?通過(guò)平面上幾個(gè)定點(diǎn)的最短路[J];福州大學(xué)學(xué)報(bào)(自然科學(xué)版);1986年01期

相關(guān)會(huì)議論文 前10條

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

2 施欣;;隨機(jī)運(yùn)輸網(wǎng)絡(luò)最短路分布研究[A];復(fù)雜巨系統(tǒng)理論·方法·應(yīng)用——中國(guó)系統(tǒng)工程學(xué)會(huì)第八屆學(xué)術(shù)年會(huì)論文集[C];1994年

3 朱建明;沙丹;;時(shí)變網(wǎng)絡(luò)中任意等待時(shí)間最短路問(wèn)題的一個(gè)對(duì)偶算法(英文)[A];第四屆中國(guó)智能計(jì)算大會(huì)論文集[C];2010年

4 俞洋;田亞菲;;一種新的變步長(zhǎng)LMS算法及其仿真[A];通信理論與信號(hào)處理新進(jìn)展——2005年通信理論與信號(hào)處理年會(huì)論文集[C];2005年

5 牛宏睿;李平;史天運(yùn);;應(yīng)急資源調(diào)度中最短路邊權(quán)不確定性問(wèn)題的建模與仿真[A];2009年中國(guó)智能自動(dòng)化會(huì)議論文集（第七分冊(cè)）[南京理工大學(xué)學(xué)報(bào)（增刊）][C];2009年

6 周顥;劉振華;趙保華;;構(gòu)造型的D~2FA生成算法[A];中國(guó)通信學(xué)會(huì)通信軟件技術(shù)委員會(huì)2009年學(xué)術(shù)會(huì)議論文集[C];2009年

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

8 劉遠(yuǎn)新;鄧飛其;羅艷輝;舒添慧;;ERP柔性平臺(tái)下物流運(yùn)輸配送系統(tǒng)算法分析[A];第二十六屆中國(guó)控制會(huì)議論文集[C];2007年

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

10 王萬(wàn)青;張曉輝;;改進(jìn)的A~*算法的高效實(shí)現(xiàn)[A];2009全國(guó)測(cè)繪科技信息交流會(huì)暨首屆測(cè)繪博客征文頒獎(jiǎng)?wù)撐募痆C];2009年

相關(guān)重要報(bào)紙文章 前1條

1 科文;VIXD算法分析Web異常[N];中國(guó)計(jì)算機(jī)報(bào);2008年

相關(guān)博士學(xué)位論文 前10條

1 吳六三;基于網(wǎng)絡(luò)熵的網(wǎng)絡(luò)可靠性研究[D];南京航空航天大學(xué);2014年

2 魏哲學(xué);樣本斷點(diǎn)距離問(wèn)題的算法與復(fù)雜性研究[D];山東大學(xué);2015年

3 劉春明;基于增強(qiáng)學(xué)習(xí)和車輛動(dòng)力學(xué)的高速公路自主駕駛研究[D];國(guó)防科學(xué)技術(shù)大學(xué);2014年

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

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

6 卜晨陽(yáng);演化約束優(yōu)化及演化動(dòng)態(tài)優(yōu)化求解算法研究[D];中國(guó)科學(xué)技術(shù)大學(xué);2017年

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

8 劉新旺;多核學(xué)習(xí)算法研究[D];國(guó)防科學(xué)技術(shù)大學(xué);2013年

9 于濱;城市公交系統(tǒng)模型與算法研究[D];大連理工大學(xué);2006年

10 曾國(guó)強(qiáng);改進(jìn)的極值優(yōu)化算法及其在組合優(yōu)化問(wèn)題中的應(yīng)用研究[D];浙江大學(xué);2011年

相關(guān)碩士學(xué)位論文 前10條

1 魏翔宇;面向最短路的網(wǎng)絡(luò)阻斷問(wèn)題研究[D];國(guó)防科學(xué)技術(shù)大學(xué);2014年

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

3 蘇健;自動(dòng)波方法求解TSP問(wèn)題[D];西安電子科技大學(xué);2004年

4 雷芬;隨機(jī)網(wǎng)絡(luò)中的動(dòng)態(tài)最短路研究[D];中央民族大學(xué);2009年

5 張振抻;網(wǎng)絡(luò)最短路的解集結(jié)構(gòu)及有關(guān)問(wèn)題[D];鄭州大學(xué);2002年

6 張美玲;最短路問(wèn)題的一個(gè)改進(jìn)蟻群算法[D];蘭州大學(xué);2008年

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

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

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

10 殷文華;移動(dòng)容遲網(wǎng)絡(luò)中基于社會(huì)感知的多播分發(fā)算法研究[D];內(nèi)蒙古大學(xué);2015年

，

本文編號(hào)：1547701