求解最短路徑的Dijkstra算法

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

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

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

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

5、不存在有向邊 的權(quán)，則 edgesIj的權(quán)為無窮大(可取值為INF=32570)。設(shè)S為一個(gè)集合，其中的每個(gè)元素表示 一個(gè)城市，求出從源點(diǎn)(自定義)城市到這些頂點(diǎn)城市的最短距離。S的初態(tài)只包含頂點(diǎn) V0。數(shù)組dist記錄從V0到其他各城市當(dāng)前的最短距離，其初值distI=edgesV0I。從S 之外的頂點(diǎn)集合V-S中選出一個(gè)城市u。使distw的值最小。于是從源點(diǎn)到達(dá)u只通過S 中的城市，把u加入集合S中調(diào)整dist中記錄的從源點(diǎn)到V-S中每個(gè)城市V的距離：從原 來的distv和distw+edgeswv中選擇較小的值作為新的distv。重復(fù)上述過程，直到 S中包含V中其余頂點(diǎn)的最短路徑。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采用鄰接矩陣的存儲(chǔ)結(jié)構(gòu)2.1圖的鄰接矩陣可以使用一個(gè)二維數(shù)組存儲(chǔ)頂點(diǎn)之間相鄰關(guān)系的鄰接矩陣，和一個(gè)具有N 個(gè)元素的一維數(shù)組存儲(chǔ)頂點(diǎn)信息，其中下標(biāo)為i的元素存儲(chǔ)頂點(diǎn)Vi的信息。2.2算法描述：void Creatdl(vexlist Gadjmatrix GA,int n,int e)int I,j,k,w;cout”輸入門個(gè)頂點(diǎn) ”endlfor(I=0;IGVI;for(I=0;In;I+)for(j=o;jn;j+)if(I=j)GAIj=o;elseGA

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

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

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

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

12、，請輸入相應(yīng)的代碼，第一個(gè)輸入的是出發(fā)弛也也 小飛 苣JL.也也 小飛 苣JL.巨JI-.巨JI-.巨JI- 時(shí)Hi:4r5信信信信 2矗善 也也城城城 AtGt入入入4 D地5 E地6 F地10 J弛 11 Kt也 12 L 設(shè)一條.圖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若長度為。則表示無法到達(dá)或在本地=謝謝使用H叫路徑查訊系統(tǒng)，如果想退出請輸入，任意鍵繼續(xù):圖4輸出最短路徑七、參考書目1徐孝凱數(shù)據(jù)結(jié)構(gòu)實(shí)用教程，清華大學(xué)出版社，1999年12月第1版。2譚浩強(qiáng)c語言程序設(shè)計(jì)，清華大學(xué)出版社。3李春葆數(shù)據(jù)結(jié)構(gòu)習(xí)題與解析，清華大學(xué)出版社，2004年2月第2版。4數(shù)據(jù)結(jié)構(gòu)-C+語言描述，人民郵電出版社，2005年三月第1版。5數(shù)據(jù)結(jié)構(gòu)（C語言描述），清華大學(xué)出版社，2004年十月第1版。八、附錄：帶注

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

15、EX; 邊的集合圖的鄰接矩陣類型通過用戶交互產(chǎn)生一個(gè)有向圖的鄰接矩陣圖的鄰接矩陣類型通過用戶交互產(chǎn)生一個(gè)有向圖的鄰接矩陣AdjMaxix creatmgraph()int i,j,k,w,n,e;int b,t;AdjMaxix adj;對圖的所有信息進(jìn)行逐步輸入coutn;while(nMAX|n0)cout城市個(gè)數(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輸入的起點(diǎn)城市不存在!n”;abort();j=0;while(j=n)cout輸入的終點(diǎn)不存在!n”;abort();adj.edgesij=w;return(adj);void dispmgraph(AdjMaxix adj)/用于輸出一個(gè)有向圖的鄰接矩陣 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計(jì)算最短路徑/輸出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置空路徑初始化源點(diǎn)編號(hào)v0放入s中循環(huán)直到所有頂點(diǎn)的最短路徑都求出選取不在s中且具有最小距離的頂點(diǎn)u頂點(diǎn)u加入s中修改不在s中的頂點(diǎn)的距離if(g.edgesujINF & distu+g.edgesujdistj)distj=distu+g.edgesuj;pathj=u;printf(輸出最短路徑:n);DisPath(dist,path,s,n,v0);輸出最短路徑void change(int num)選擇語句用于替換頂點(diǎn)值，輸出名稱switch(num)case 1: printf(A 地);break;case 2: printf(B 地);break;case 3:printf(C