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

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

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

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

4、問題大都不含負權所以我們在的情況下選擇Dijkstra算法)0(?ijw定義定義1若圖中各邊e都賦有一個實數稱為邊的權則稱這種圖為賦)(EVGG?)(eWe權圖記為.)(WEVGG?定義定義2若圖是賦權圖且若u是到的路的權則)(EVGG?)(0)(GEeeW??ivjv)(uW稱為的長長最小的到的路稱為最短路.若要找出從到的通路)(uWuiVjV)(uWivnvu使全長最短即.????minijeuWuWe???2.22.2各類最短路算

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

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

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

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

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

10、撲排序，以判斷是否存在負權回路.我們用數組記錄每個結點的最短路徑估計值，而且用鄰接表來存儲圖.我們采取DG的方法是松弛：設立一個先進先出的隊列用來保存待優(yōu)化的結點，優(yōu)化時每次取出隊首結點，并且用點當前的最短路徑估計值對離開點所指向的結點進行松弛操作，如UUUV果點的最短路徑估計值有所調整，且點不在當前的隊列中，就將點放入隊尾.這樣VVV不斷從隊列中取出結點來進行松弛操作，直至隊列空為止.每次將點放入隊尾，都是經過松弛操作達到的.換言之，

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