求解最短路徑的Dijkstra算法

1、一、問題分析與任務定義本題主要是利用Dijkstra算法來求解頂點之間最短路徑，其中包括如下幾個待解決的問 題：1問題分析選擇合適的結構表示圖主要包括：用Dijkstra算法實現(xiàn)起來更要容易；時間復雜度?。?自己可以熟練應用。Dijstra算法的實現(xiàn)所應涉及到的各參數(shù)及變量：頂點的編號；各邊權 的初使化；如何求出從頂點到其他各點的最短距離；最短距離長度的求取等問題。2任務定義對任意圖，選擇合適的數(shù)據(jù)結構表示圖，在此基礎上實現(xiàn)求解最短路徑的Dijkstra算 法。要求：對所設計的圖的數(shù)據(jù)結構，提供必要的基本功能。在帶權的有向圖中源點到終點的多條路徑中尋找出一條各邊權植之和最小的路徑，即最 短路徑

2、。對任務的理解考慮設計的圖結構是否具備必要的基本功能，具有實際的應用；圖的鄰接 矩陣如何實現(xiàn)交互式；如何將輸入的鄰接矩陣溶入到dijstra算法中去。需要解決什么樣的 實際問題。并且能夠將程序與實際問題相結合，能夠處理一般的最短路徑問題。二、概要設計和數(shù)據(jù)結構的選擇按路徑長度遞增的順序產(chǎn)生最短路徑。通過以上對問題的分析和任務的理解，設計出一 個大體的模塊和程序流程。1程序中涉及到的結構體及子函數(shù)：1.1結構體：本程序設計使用了以下結構體：struct vertex int num;頂點編號int data;頂點信息;頂點類型typedef struct graphint n;圖中頂點個數(shù)int

3、 e;圖中邊的個數(shù)struct vertex vexsMAXVEX; 頂點集合int edgesMAXVEXMAXVEX; 邊的集合AdjMaxix;圖的鄰接矩陣類型1.2子函數(shù)：設計本程序需分成幾個模塊，要用到以下幾個子函數(shù)：AdjMaxix creatmgraph() 通過用戶交互產(chǎn)生一個有向圖的鄰接矩陣；void dispmgraph(AdjMaxix adj)/用于輸出一個有向圖的鄰接矩陣；void ppath(int path,int i,int v0)；選擇輸出一條最短路徑void DisPath(int dist,int path,int s,int n,int v0)用path

4、計算最短路徑void Dijkstra(AdjMaxix g,int v0) / Dijkstra 算法void change(int num)用于替換頂點編號、詳細設計和編碼這里設計用鄰接矩陣解決實際生活中城市間往返最短路徑問題。1算法思想把圖中頂點集合分成兩組，第一組為集合S，存放已求出其最短路徑的頂點，第二組為 尚未確定最短路徑的頂點集合是V-S (用U表示)，其中V為網(wǎng)中所有頂點集合。在這里我 們設計一個有向圖G=(V，E)為G地區(qū)的交通圖。1.1在這個圖中，V= (1，2, ，N)代表各個城市。edges是表示G的鄰接矩陣，edgesIj 表示有向邊的權，這里的權值代表城市間距離。若

5、不存在有向邊 的權，則 edgesIj的權為無窮大(可取值為INF=32570)。設S為一個集合，其中的每個元素表示 一個城市，求出從源點(自定義)城市到這些頂點城市的最短距離。S的初態(tài)只包含頂點 V0。數(shù)組dist記錄從V0到其他各城市當前的最短距離，其初值distI=edgesV0I。從S 之外的頂點集合V-S中選出一個城市u。使distw的值最小。于是從源點到達u只通過S 中的城市，把u加入集合S中調整dist中記錄的從源點到V-S中每個城市V的距離：從原 來的distv和distw+edgeswv中選擇較小的值作為新的distv。重復上述過程，直到 S中包含V中其余頂點的最短路徑。1.

6、2算法描述：void Dijkstra(AdjMaxix g,int v0)int distMAXVEX,pathMAXVEX;int sMAXVEX;int mindis,i,j,u,n=g.n;for(i=0;in;i+)disti=g.edgesv0i;si=0;if(g.edgesv0iINF)pathi=v0;elsepathi=-1;sv0=1;pathv0=0;for(i=0;in;i+)mindis=INF;u=-1;for(j=0;jn;j+)if(sj=0 & distjmindis)u=j;mindis=distj;su=1;for(j=0;jn;j+)if(sj=0)i

7、f(g.edgesujINF&distu+g.edgesujdistj)distj=distu+g.edgesuj; pathj=u;2采用鄰接矩陣的存儲結構2.1圖的鄰接矩陣可以使用一個二維數(shù)組存儲頂點之間相鄰關系的鄰接矩陣，和一個具有N 個元素的一維數(shù)組存儲頂點信息，其中下標為i的元素存儲頂點Vi的信息。2.2算法描述：void Creatdl(vexlist Gadjmatrix GA,int n,int e)int I,j,k,w;cout”輸入門個頂點 ”endlfor(I=0;IGVI;for(I=0;In;I+)for(j=o;jn;j+)if(I=j)GAIj=o;elseGA

8、Ij=MaxValue;cout”輸入”。”條邊 ”endlfor(k=1;kIjw;GAIj=GAIj=w;四、上機調試對設計實現(xiàn)的回顧討論和分析；算法的時、空性能分析和改進設想，經(jīng)驗和體會等。1調試中遇到的問題與解決方法1.1在進行輸入輸出語句的調試時，系統(tǒng)提示無法識別函數(shù)，缺少頭文件;1.2出現(xiàn)重大錯誤，多達數(shù)百條錯誤，著實郁悶了一陣 很多標點符號是在中文輸入法狀態(tài) 下輸入，造成系統(tǒng)無法識別，改掉后錯誤消失；如switch語句，在每條選擇語句后，缺少break。，錯誤；1.3函數(shù)方法使用有誤，無法通過；在賦實參時，對于變化的實參只需賦初值，子函數(shù)也可 以調用子函數(shù)；1.4困惑很久的調用子

9、函數(shù)問題，在賦實參時找不到實參;用switch語句進行相關選擇代換， 成功。1.5連系實際問題上，int型與char型的替換上不知道用什么函數(shù)實現(xiàn)；2設計體會對C語言的使用不是很熟練，造成自己浪費很多時間在復習C語言，如：結構體的使用， 不能靈活應用do,while( )，switch()語句等；調用子函數(shù)問題上，子函數(shù)之間錯綜復雜的 調用和實參，形參的賦值讓自己很是迷惑，三天時間，也許更多時間里，都是在研究怎樣調 用子函數(shù)。雖然最后基本是完成了教授布置下來的課程設計，但是還是有不盡人意的地方： 結點的插入，刪除，路徑的實際化最終由于時間問題沒能解決，很遺憾。程序缺乏人性化設 計，估計第一次使

10、用本程序的人會很迷茫。3時間空間復雜度的計算利用Dijkstra算法求解最短路徑時，求每一對頂點之間的最短路徑的一種方法是反復執(zhí)行 n次Dijkstra算法，每次執(zhí)行以一個頂點為源點，求得從該頂點到其它各頂點的最短路徑； 其時間復雜度為O(n3)。其空間的復雜度為o(n)。五、用戶使用說明本程序主要是用來計算從某一點到其他各點的最短路徑長度，第一次使用可能會有點迷 茫，但是它卻是本人兩周來的血汗，如有不便請原諒。下面描述該使用方法：程序會在一開 始讓用戶輸入結點數(shù)，線路數(shù)，然后輸入相關結點信息，有城市名字(只能使用英文名稱)， 線路長度，起點城市，終點城市。接下來都由計算機完成。結果會輸出源點

11、到各城市間的長 度。六、測試結果輸入數(shù)據(jù)：輸入城市數(shù)為：4輸入城市線路為：4然后輸入城市信息(這里每個數(shù)字代表1 A地2 B地3 C地4 D地):輸入第一個城市信息：1 輸入第一個城市信息：2 輸入第二個城市信息：3 輸入第四個城市信息：4 輸入第一條線路的起點：1，終點：3線路長度為KM：56輸入第二條線路的起點：2，終點：3線路長度為KM：78輸入第二條線路的起點：1，終點：2線路長度為KM：89輸入第二條線路的起點：3，終點：4線路長度為KM：99下面是結果截圖:c：,- *C: DocuAent s and Sett ingsuser桌面Debugks. exeF面每個數(shù)字代表一個城市

12、，請輸入相應的代碼，第一個輸入的是出發(fā)弛也也 小飛 苣JL.也也 小飛 苣JL.巨JI-.巨JI-.巨JI- 時Hi:4r5信信信信 2矗善 也也城城城 AtGt入入入4 D地5 E地6 F地10 J弛 11 Kt也 12 L 設一條.圖3輸入所有城市信息圖3輸入所有城市信息0：,- *C: DocuAent s and Sett ingsuser桌面Debugks. exe輸出線路的矩陣表示：-101230 12 38 8 8 8徑 在短短短各地地地地路。首取到油BCD短不的的的地一一一 一最發(fā)一輸 A-.fl:.fl:3路路路路地890 12 38 8 8 8徑 在短短短各地地地地路。首取

13、到油BCD短不的的的地一一一 一最發(fā)一輸 A-.fl:.fl:3路路路路地898 8 856788 88 8998,3,3,3程:0:0:0咯短Km01 2 3 3 3若長度為。則表示無法到達或在本地=謝謝使用H叫路徑查訊系統(tǒng)，如果想退出請輸入，任意鍵繼續(xù):圖4輸出最短路徑七、參考書目1徐孝凱數(shù)據(jù)結構實用教程，清華大學出版社，1999年12月第1版。2譚浩強c語言程序設計，清華大學出版社。3李春葆數(shù)據(jù)結構習題與解析，清華大學出版社，2004年2月第2版。4數(shù)據(jù)結構-C+語言描述，人民郵電出版社，2005年三月第1版。5數(shù)據(jù)結構（C語言描述），清華大學出版社，2004年十月第1版。八、附錄：帶注

14、釋的源程序 TOC o 1-5 h z /*/*/*用Dijkstra算法求出有向圖中某個源點到其他各頂點的最短路徑長度*/*/*/#include #include #include #include #define INF 32767#define MAXVEX 100#define MAX 12 struct vertex頂點編號頂點的信息頂點編號頂點的信息頂點類型int data;typedef struct graphint n;圖中頂點的個數(shù)和邊的個數(shù)int e;圖中頂點的個數(shù)和邊的個數(shù)struct vertex vexsMAXVEX;頂點集合int edgesMAXVEXMAXV

15、EX; 邊的集合圖的鄰接矩陣類型通過用戶交互產(chǎn)生一個有向圖的鄰接矩陣圖的鄰接矩陣類型通過用戶交互產(chǎn)生一個有向圖的鄰接矩陣AdjMaxix creatmgraph()int i,j,k,w,n,e;int b,t;AdjMaxix adj;對圖的所有信息進行逐步輸入coutn;while(nMAX|n0)cout城市個數(shù)不正確!請重新輸入!”n;coute;adj.n=n;adj.e=e;cout輸入城市信息:n;for(i=0;in;i+)cout第i+1adj.vexsi.data;adj.vexsi.num=i;for(i=0;in;i+)for(j=0;jn;j+)adj.edgesij

16、=0;for(k=0;ke;k+)cout第k+1”條線路:endl;coutb;coutt;coutw;i=0;while(i=n)cout輸入的起點城市不存在!n”;abort();j=0;while(j=n)cout輸入的終點不存在!n”;abort();adj.edgesij=w;return(adj);void dispmgraph(AdjMaxix adj)/用于輸出一個有向圖的鄰接矩陣 int i,j,n,e; n=adj.n;e=adj.e;cout輸出線路的矩陣表示:endl;cout;for(i=-1;in;i+)printf(%6d,i);printf(n);couten

17、dl;for(i=0;in;i+)printf(%6d,i);for(j=0;jn;j+)if(adj.edgesij=0)printf(%6s”,8”)；elseprintf(%6d,adj.edgesij); coutendl;void ppath(int path,int i,int v0)int k;k=pathi;if(k=v0)return;ppath(path,k,v0);printf(%d,k);void DisPath(int dist,int path,int s,int n,int v0)用path用path計算最短路徑/輸出path值printf( path:);for

18、(i=0;in;i+)printf(%3d,pathi);printf(n);用于輸出最短路徑和路徑長度for(i=0;in;i+)用于輸出最短路徑和路徑長度if(si=1 & i!=v0)printf(M%d到d的最短路徑為巴v0,i);printf(%d,”,v0);ppath(path,i,v0);printf(%dn”,i);elseprintf(M%d 到d 不存在路徑n,v0,i);void Dijkstra(AdjMaxix g,int v0)int distMAXVEX,pathMAXVEX;int sMAXVEX;int mindis,i,j,u,n=g.n;void Dij

19、kstra(AdjMaxix g,int v0)int distMAXVEX,pathMAXVEX;int sMAXVEX;int mindis,i,j,u,n=g.n;for(i=0;in;i+)disti=g.edgesv0i;si=0;if(g.edgesv0iINF)pathi=v0;elsepathi=-1;sv0=1;pathv0=0;for(i=0;in;i+)mindis=INF;u=-1;for(j=0;jn;j+)if(sj=0 & distjmindis)u=j;mindis=distj;su=1;for(j=0;jn;j+)if(sj=0)距離初始化/s置空路徑初始化源點編號v0放入s中循環(huán)直到所有頂點的最短路徑都求出選取不在s中且具有最小距離的頂點u頂點u加入s中修改不在s中的頂點的距離if(g.edgesujINF & distu+g.edgesujdistj)distj=distu+g.edgesuj;pathj=u;printf(輸出最短路徑:n);DisPath(dist,path,s,n,v0);輸出最短路徑void change(int num)選擇語句用于替換頂點值，輸出名稱switch(num)case 1: printf(A 地);break;case 2: printf(B 地);break;case 3:printf(C