基于Dijkstra算法求有向帶權圖的最短路徑

1、 湖北大學本科學年論文 題 目 單源最短路徑算法分析與研究 姓 名 夏臻 學 號 2012221104230007 專業(yè)年級 2012級信息安全 指導教師 馬傳香 職 稱 教授 成績 2014年 12 月 02 日目錄一、摘要1二、最短路徑22.1最短路徑的定義22.2最短路徑解決算法32.2.1 Dijkstra算法32.2.2 A*算法32.2.3 SPFA算法32.2.4 Bellman-Ford算法32.2.5 floyd-warshall算法4三、Dijkstra算法實現(xiàn)單源最短路徑43.1最短路徑的最優(yōu)子結構性質43.2 Dijkstra算法思路43.3 Dijkstra算法描述5

2、四、Dijkstra算法測試64.1測試數據64.2運行結果6五、心得體會6六、參考文獻7七、附錄8一、摘要最短路徑問題是圖論理論的一個經典問題。尋找最短路徑就是在指定的網絡中兩節(jié)點間找到一條距離最小的路。最短路徑算法的選擇與實現(xiàn)是通路設計的基礎，是計算機與信息科學等領域研究的熱點問題。很多與時間、費用、線路容量等許許多多的實際問題都要運用最短路徑的算法原理來解決，生活中很多的問題的解決離不開這些算法，隨著計算機結構的改變以及數據結構的研究與發(fā)展，新的有效的算法不斷涌現(xiàn)。本文是來對最短路徑的算法包括Dijkstra算法、Floyd-Warshall算法、Bellman-Ford算法、SPFA快

3、速算法做一些分析和研究。分析這幾種算法的目的在于更好的理解求解單源最短路徑問題解題思路，從而嘗試著是否能研究出更好的算法。關鍵詞：單源最短路徑 圖論 Dijkstra算法 Floyd-Warshall算法 Bellman-Ford 算法 SPFA算法 二、最短路徑2.1最短路徑的定義最短路徑問題是圖論研究中的一個經典算法問題，旨在尋找圖（由結點和路徑組成的）中兩結點之間的最短路徑。算法具體的形式包括：1.確定起點的最短路徑問題-即已知起始結點，求最短路徑的問題2.確定終點的最短路徑問題-與確定起點的問題相反，該問題是已知終點結點，求最短路徑的問題。在無向圖中該問題與確定起點的問題完全等同，在有

4、向圖中該問題就等同于把所有路徑方向反轉的確定起點的問題。3. 確定起點終點的最短路徑問題 - 即已知起點和終點，求兩結點之間的最短路徑。4. 全局最短路徑問題 - 求圖中所有的最短路徑。2.2最短路徑解決算法2.2.1 Dijkstra算法迪杰斯特拉算法是由荷蘭計算機科學家狄克斯特拉于1959 年提出的，因此又叫狄克斯特拉算法。是從一個頂點到其余各頂點的最短路徑算法，解決的是有向圖中最短路徑問題。迪杰斯特拉算法主要特點是以起始點為中心向外層層擴展，直到擴展到終點為止。2.2.2 A*算法A*算法；A*（A-Star)算法是一種靜態(tài)路網中求解最短路最有效的直接搜索方法。估價值與實際值越接近，估價

5、函數取得就越好。2.2.3 SPFA算法SPFA（Shortest Path Faster Algorithm）算法是求單源最短路徑的一種算法，在Bellman-ford算法的基礎上加上一個隊列優(yōu)化，減少了冗余的松弛操作，是一種高效的最短路算法。2.2.4 Bellman-Ford算法Bellman-ford算法是求含負權圖的單源最短路徑算法，效率很低，但代碼很容易寫。即進行不停地松弛（原文是這么寫的，為什么要叫松弛，爭議很大），每次松弛把每條邊都更新一下，若n-1次松弛后還能更新，則說明圖中有負環(huán)，無法得出結果，否則就成功完成。Bellman-ford算法有一個小優(yōu)化：每次松弛先設一個標識f

6、lag，初值為FALSE，若有邊更新則賦值為TRUE，最終如果還是FALSE則直接成功退出。Bellman-ford算法浪費了許多時間做無必要的松弛，所以SPFA算法用隊列進行了優(yōu)化，效果十分顯著，高效難以想象。SPFA還有SLF，LLL，滾動數組等優(yōu)化。2.2.5 floyd-warshall算法Floyd-Warshall算法是解決任意兩點間的最短路徑的一種算法。通常可以在任何圖中使用，包括有向圖、帶負權邊的圖。三、Dijkstra算法實現(xiàn)單源最短路徑3.1最短路徑的最優(yōu)子結構性質該性質描述為：如果P(i,j)=Vi.Vk.Vs.Vj是從頂點i到j的最短路徑，k和s是這條路徑上的一個中間頂

7、點，那么P(k,s)必定是從k到s的最短路徑。下面證明該性質的正確性。 假設P(i,j)=Vi.Vk.Vs.Vj是從頂點i到j的最短路徑，則有P(i,j)=P(i,k)+P(k,s)+P(s,j)。而P(k,s)不是從k到s的最短距離，那么必定存在另一條從k到s的最短路徑P'(k,s)，那么P'(i,j)=P(i,k)+P'(k,s)+P(s,j)<P(i,j)。則與P(i,j)是從i到j的最短路徑相矛盾。因此該性質得證。3.2 Dijkstra算法思路 由上述性質可知，如果存在一條從i到j的最短路徑(Vi.Vk,Vj)，Vk是Vj前面的一頂點。那么(Vi.Vk)

8、也必定是從i到k的最短路徑。為了求出最短路徑，Dijkstra就提出了以最短路徑長度遞增，逐次生成最短路徑的算法。譬如對于源頂點V0，首先選擇其直接相鄰的頂點中長度最短的頂點Vi，那么當前已知可得從V0到達Vj頂點的最短距離distj=mindistj,disti+matrixij。根據這種思路，假設存在G=<V,E>，源頂點為V0，U=V0,disti記錄V0到i的最短距離，pathi記錄從V0到i路徑上的i前面的一個頂點。1.從V-U中選擇使disti值最小的頂點i，將i加入到U中；2.更新與i直接相鄰頂點的dist值。(distj=mindistj,disti+matrixi

9、j)3.知道U=V，停止。3.3 Dijkstra算法描述 procdure SHORTEST-PATHS(v,COST,DIST,n) /G是一個有向圖,它由其成本鄰接矩陣COST(n,n)表示,DIST(j)被置成以節(jié)點v到節(jié)點j的最短路徑長度,這里1<=j<=n;DIST(v)被置成零/ boolean S(1:n);real COST(1:n,1:n) ,DIST(1:n) integer u,v,n,num,i,w; for i<-1 to n do S(i)<-0;DIST(i)<-COST(v,i) repeat S(v)<-1;DIST(v)

10、<-0; for num<-2 to n-1 do 選取結點u，它使得DIST(u)=minDIST(w) S(u)<-1 for 所有S(w)=0的結點w do DIST(w)<-min(DIST(w),DIST(u)+COST(u,w) repeat repeat end SHORTEST-PATHS 四、Dijkstra算法測試4.1測試數據4.2運行結果五、心得體會通過Dijkstra算法求有向帶權圖的最短路徑問題實驗，了解了解決一個問題可以有多種方法，不同方法有著各自的優(yōu)缺點，在不同特定的情況下都有各自發(fā)揮狀態(tài)。不過，應該指出：用實例的運行時間來度量算法的時間

11、復雜性并不合適，因為這個實例時間與運行該算法的實際計算機性能有關。換句話說，這個實例時間不單純反映算法的效率而是反映包括運行該算法的計算機在內的綜合效率。我們引入算法復雜性的概念是為了比較解決同一個問題的不同算法的效率，而不想去比較運行該算法的計算機的性能。因而，不應該取算法運行的實例時間作為算法復雜性的尺度。我們希望，盡量單純地反映作為算法精髓的計算方法本身的效率，而且在不實際運行該算法的情況下就能分析出它所需要的時間和空間。六、參考文獻1 王曉東. 計算機算法設計與分析第3版. 電子工業(yè)出版社,2007. 2 嚴蔚敏，吳偉民.數據結構（C語言版）. 清華大學出版社,1996. 3 余詳宣，

12、崔國華，鄒海明. 計算機算法基礎. 華中科技大學出社,2007 4 鄭宗漢，鄭曉明. 算法設計與分析. 清華大學出版設,2005 5 黃劉生，唐策善.數據結構第二版.中國科學技術大學出版社，2000七、附錄#include <iostream>#include<stack>#define M 100#define N 100using namespace std;typedef struct node int matrixNM; /鄰接矩陣 int n; /頂點數 int e; /邊數 MGraph; void DijkstraPath(MGraph g,int *di

13、st,int *path,int v0) /v0表示源頂點 int i,j,k; bool *visited=(bool *)malloc(sizeof(bool)*g.n); for(i=0;i<g.n;i+) /初始化 if(g.matrixv0i>0&&i!=v0) disti=g.matrixv0i; pathi=v0; /path記錄最短路徑上從v0到i的前一個頂點 else disti=INT_MAX; /若i不與v0直接相鄰，則權值置為無窮大 pathi=-1; visitedi=false; pathv0=v0; distv0=0; visitedv

14、0=true; for(i=1;i<g.n;i+) /循環(huán)擴展n-1次 int min=INT_MAX; int u; for(j=0;j<g.n;j+) /尋找未被擴展的權值最小的頂點 if(visitedj=false&&distj<min) min=distj; u=j; visitedu=true; for(k=0;k<g.n;k+) /更新dist數組的值和路徑的值 if(visitedk=false&&g.matrixuk>0&&min+g.matrixuk<distk) distk=min+g.m

15、atrixuk; pathk=u; void showPath(int *path,int v,int v0) /打印最短路徑上的各個頂點 stack<int> s; int u=v; while(v!=v0) s.push(v); v=pathv; s.push(v); while(!s.empty() cout<<s.top()<<" " s.pop(); int main(int argc, char *argv) int n,e; /表示輸入的頂點數和邊數 while(cin>>n>>e&&e!=0) int i,j; int s,t,w; /表示存在一條邊s->t,權值為w MGraph g; int v0; int *dist=(int *)malloc(sizeof(int)*n); int *path=(int *)malloc(sizeof(int)*n); for(i=0;i<N;i+) for(j=0;j<M;j+) g.