最短路徑畢業(yè)論文

1、安慶師范學(xué)院數(shù)學(xué)與計(jì)算數(shù)學(xué)學(xué)院2013屆畢業(yè)論文第1頁(yè)共9頁(yè)最短路算法的比較與應(yīng)用最短路算法的比較與應(yīng)用作者：胡義棚指導(dǎo)老師：丁超摘要：摘要：本文較詳盡地介紹了最短路算法相關(guān)的基本概念，給出了Dijkstra算法、Floyd算法、SPFA算法等常用算法及其核心思想，并對(duì)各種最短算法做了多角度的比較，闡述了各種算法的應(yīng)用范圍，并對(duì)其在運(yùn)輸網(wǎng)絡(luò)、艦船通道路線設(shè)計(jì)、工業(yè)生產(chǎn)中的應(yīng)用做出了舉例說(shuō)明，側(cè)重于模型的建立、思考和證明的過(guò)程，最后作出總

2、結(jié).關(guān)鍵詞：關(guān)鍵詞：最短路算法Dijkstra算法Floyd算法SPFA算法一、引言一、引言最短路算法是圖論中的核心問(wèn)題之一，他是許多更深層次算法的基礎(chǔ)，同時(shí)，該問(wèn)題有著大量的生產(chǎn)實(shí)際的背景.很多問(wèn)題從表面上看與最短問(wèn)題沒(méi)有什么關(guān)系.卻也可以歸結(jié)為最短路問(wèn)題，本文通過(guò)收集整理關(guān)于最短路徑的普遍算法，為研究最短路徑問(wèn)題在一些出行問(wèn)題，工程問(wèn)題，及實(shí)際生活問(wèn)題中的應(yīng)用，為企業(yè)和個(gè)人提供方便的選擇方法.二、最短路二、最短路2.12.1最短路的

3、定義最短路的定義對(duì)最短路問(wèn)題的研究早在上個(gè)世紀(jì)60年代以前就卓有成效了其中對(duì)賦權(quán)的)0(?ijw有效算法是由荷蘭著名計(jì)算機(jī)專(zhuān)家E.W.Dijkstra在1959年首次提出的該算法能夠解決兩指定點(diǎn)間的最短路也可以求解圖G中一特定點(diǎn)到其它各頂點(diǎn)的最短路.后來(lái)海斯在Dijkstra算法的基礎(chǔ)之上提出了海斯算法.但這兩種算法都不能解決含有負(fù)權(quán)的圖的最短路問(wèn)題.因此由Fd提出了Fd算法它能有效地解決含有負(fù)權(quán)的最短路問(wèn)題.但在現(xiàn)實(shí)生活中我們所遇到的

4、問(wèn)題大都不含負(fù)權(quán)所以我們?cè)诘那闆r下選擇Dijkstra算法)0(?ijw定義定義1若圖中各邊e都賦有一個(gè)實(shí)數(shù)稱(chēng)為邊的權(quán)則稱(chēng)這種圖為賦)(EVGG?)(eWe權(quán)圖記為.)(WEVGG?定義定義2若圖是賦權(quán)圖且若u是到的路的權(quán)則)(EVGG?)(0)(GEeeW??ivjv)(uW稱(chēng)為的長(zhǎng)長(zhǎng)最小的到的路稱(chēng)為最短路.若要找出從到的通路)(uWuiVjV)(uWivnvu使全長(zhǎng)最短即.????minijeuWuWe???2.22.2各類(lèi)最短路算

5、法的介紹各類(lèi)最短路算法的介紹2.2.12.2.1FloydFloyd算法算法Floyd算法又稱(chēng)為弗洛伊德算法，插點(diǎn)法，是一種用于尋找給定的加權(quán)圖中頂點(diǎn)間最短路徑的算法.該算法名稱(chēng)以創(chuàng)始人之一、1978年圖靈獎(jiǎng)獲得者、斯坦福大學(xué)計(jì)算機(jī)科學(xué)系教授羅伯特弗洛伊德命名.其核心思路是通過(guò)一個(gè)圖的權(quán)值矩陣求出它的每?jī)牲c(diǎn)間的最短路徑矩陣.即從圖的帶權(quán)鄰接矩陣開(kāi)始，遞歸地進(jìn)行n次更新，即由矩陣，按一個(gè)公式，2)]([njiaA?AD?)0(構(gòu)造出矩陣；

6、又用同樣地公式由構(gòu)造出；……；最后又用同樣的公式由)1(D)1(D)2(D構(gòu)造出矩陣.矩陣的行列元素便是號(hào)頂點(diǎn)到號(hào)頂點(diǎn)的最短路徑長(zhǎng)度，)1(D)(nD)(nDijij稱(chēng)為圖的距離矩陣，同時(shí)還可引入一個(gè)后繼節(jié)點(diǎn)矩陣path來(lái)記錄兩點(diǎn)間的最短路徑.)(nD下面介紹其算法過(guò)程：從任意一條單邊路徑開(kāi)始.所有兩點(diǎn)之間的距離是邊的權(quán)，如果兩點(diǎn)之間沒(méi)有邊相)1連，則權(quán)為無(wú)窮大安慶師范學(xué)院數(shù)學(xué)與計(jì)算數(shù)學(xué)學(xué)院2013屆畢業(yè)論文第3頁(yè)共9頁(yè)2.2.32.2

7、.3BellmanFdBellmanFd算法算法Dijkstra算法中不允許邊的權(quán)是負(fù)權(quán)，如果遇到負(fù)權(quán)，則可以采用BellmanFd算法.BellmanFd算法能在更普遍的情況下（存在負(fù)權(quán)邊）解決單源點(diǎn)最短路徑問(wèn)題.對(duì)于給定的帶權(quán)（有向或無(wú)向）圖，其源點(diǎn)為，加權(quán)函數(shù)是邊集的)(EVG?SWE映射.對(duì)圖運(yùn)行BellmanFd算法的結(jié)果是一個(gè)布爾值，表明圖中是否存在著一個(gè)從源G點(diǎn)可達(dá)的負(fù)權(quán)回路.若不存在這樣的回路，算法將給出從源點(diǎn)到圖的任意

8、頂點(diǎn)的SSGV最短路徑.][VD下面介紹其算法過(guò)程：初始化：將除源點(diǎn)外的所有頂點(diǎn)的最短距離估計(jì)值)10][][???SDVD迭代求解：反復(fù)對(duì)邊集E中的每條邊進(jìn)行松弛操作，使得頂點(diǎn)集中的每個(gè)頂點(diǎn))2V的最短距離估計(jì)值逐步逼近其最短距離（運(yùn)行次）；V1V檢驗(yàn)負(fù)權(quán)回路：判斷邊集中的每一條邊的兩個(gè)端點(diǎn)是否收斂.如果存在未收斂的)3E頂點(diǎn)，則算法返回，表明問(wèn)題無(wú)解；否則算法返回，并且從源點(diǎn)可達(dá)的頂點(diǎn)falsetrue的最短距離保存在中.v][vd

9、2.2.42.2.4SPFASPFA算法算法求單源最短路的SPFA算法的全稱(chēng)是：ShtestPathFasterAlgithm.SPFA算法由西南交通大學(xué)段凡丁于1994年發(fā)表.很多時(shí)候，給定的圖存在負(fù)權(quán)邊，這時(shí)類(lèi)似Dijkstra等算法便沒(méi)有了用武之地，而B(niǎo)ellmanFd算法的復(fù)雜度又過(guò)高，SPFA算法便派上用場(chǎng)了.下面介紹其原理與算法過(guò)程：我們約定有向加權(quán)圖不存在負(fù)權(quán)回路，即最短路徑一定存在.當(dāng)然，我們可以在執(zhí)G行該算法前做一次拓

10、撲排序，以判斷是否存在負(fù)權(quán)回路.我們用數(shù)組記錄每個(gè)結(jié)點(diǎn)的最短路徑估計(jì)值，而且用鄰接表來(lái)存儲(chǔ)圖.我們采取DG的方法是松弛：設(shè)立一個(gè)先進(jìn)先出的隊(duì)列用來(lái)保存待優(yōu)化的結(jié)點(diǎn)，優(yōu)化時(shí)每次取出隊(duì)首結(jié)點(diǎn)，并且用點(diǎn)當(dāng)前的最短路徑估計(jì)值對(duì)離開(kāi)點(diǎn)所指向的結(jié)點(diǎn)進(jìn)行松弛操作，如UUUV果點(diǎn)的最短路徑估計(jì)值有所調(diào)整，且點(diǎn)不在當(dāng)前的隊(duì)列中，就將點(diǎn)放入隊(duì)尾.這樣VVV不斷從隊(duì)列中取出結(jié)點(diǎn)來(lái)進(jìn)行松弛操作，直至隊(duì)列空為止.每次將點(diǎn)放入隊(duì)尾，都是經(jīng)過(guò)松弛操作達(dá)到的.換言之，

11、每次的優(yōu)化將會(huì)有某個(gè)點(diǎn)的最短路徑估計(jì)值變小.所以算法的執(zhí)行會(huì)使越來(lái)越小.由于我們假定圖中不存V][VDD在負(fù)權(quán)回路，所以每個(gè)結(jié)點(diǎn)都有最短路徑值.因此，算法不會(huì)無(wú)限執(zhí)行下去，隨著值的逐D漸變小，直到到達(dá)最短路徑值時(shí)，算法結(jié)束，這時(shí)的最短路徑估計(jì)值就是對(duì)應(yīng)結(jié)點(diǎn)的最短路徑值.所以只要最短路徑存在，上述SPFA算法必定能求出最小值.2.3最短算法的比較最短算法的比較2.3.12.3.1FloydFloyd算法算法求多源、無(wú)負(fù)權(quán)邊的最短路.用矩陣