求解最短路徑的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ù)定義對(duì)任意圖，選擇合適的數(shù)據(jù)結(jié)構(gòu)表示圖，在此基礎(chǔ)上實(shí)現(xiàn)求解最短路徑的算法。要求：對(duì)所設(shè)計(jì)的圖的數(shù)據(jù)結(jié)構(gòu)，提供必要的基本功能。在帶權(quán)的有向圖中源點(diǎn)到終點(diǎn)的多條路徑中尋找出一條各邊權(quán)植之和最小的路徑，即最短路徑。對(duì)任務(wù)的理解考慮設(shè)計(jì)的圖

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

3、sMAXVEX;頂點(diǎn)集合intedgesMAXVEXMAXVEX;邊的集合AdjMaxix;圖的鄰接矩陣類型1.2子函數(shù)：設(shè)計(jì)本程序需分成幾個(gè)模塊，要用到以下幾個(gè)子函數(shù)：AdjMaxixcreatmgraph()/通過用戶交互產(chǎn)生一個(gè)有向圖的鄰接矩陣；voiddispmgraph(AdjMaxixadj)/用于輸出一個(gè)有向圖的鄰接矩陣；voidppath(intpath,inti,intv0)；選擇輸出一條最短路徑voidDisPath(intdist,intpath,ints,intn,intvO)用path計(jì)算最短路徑voidDijkstra(AdjMaxixg,intvO)/Dijkst

4、ra算法voidchange(intnum)用于替換頂點(diǎn)編號(hào)1.3結(jié)構(gòu)圖與流程圖圖2程序流程圖、詳細(xì)設(shè)計(jì)和編碼這里設(shè)計(jì)用鄰接矩陣解決實(shí)際生活中城市間往返最短路徑問題。1算法思想把圖中頂點(diǎn)集合分成兩組，第一組為集合，存放已求出其最短路徑的頂點(diǎn)，第二組為尚未確定最短路徑的頂點(diǎn)集合是(用表示)，其中為網(wǎng)中所有頂點(diǎn)集合。在這里我們?cè)O(shè)計(jì)一個(gè)有向圖G=(V,E)為G地區(qū)的交通圖。1.1在這個(gè)圖中，V=(1,2,鄰鄰N)代表各個(gè)城市oedges是表示G的鄰接矩陣，edgesIj表示有向邊vi,j的權(quán)，這里的權(quán)值代表城市間距離。若不存在有向邊vi,j的權(quán)，則edgesIj的權(quán)為無窮大(可取值為INF=3257

5、0)設(shè)S為一個(gè)集合，其中的每個(gè)元素表示一個(gè)城市，求出從源點(diǎn)(自定義)城市到這些頂點(diǎn)城市的最短距離。S的初態(tài)只包含頂點(diǎn)V0o數(shù)組dist記錄從V0到其他各城市當(dāng)前的最短距離，其初值distI=edgesVOIo從S之外的頂點(diǎn)集合V-S中選出一個(gè)城市Uo使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.2算法描述：voidDijkstra(AdjMaxixg,intvO)intdistMAX

6、VEX,pathMAXVEX;intsMAXVEX;intmindis,i,j,u,n=g.n;for(i=0;ivn;i+)disti=g.edgesvOi;si=0；if(g.edgesvOivINF)pathi=vO;elsepathi=-1;sv0=1;pathv0=0;for(i=0;ivn;i+)mindis=INF;u=-1;for(j=0;jvn;j+)if(sj=O&distjvmindis)u=j;mindis=distj;su=1;for(j=O;jvn;j+)if(sj=0)if(g.edgesujvINF&distu+g.edgesujvdistj)distj=dis

7、tu+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算法描述：voidCreatdl(vexlistGV,adjmatrixGA,intn,inte)intI,j,k,w;coutvv輸入vvnvv個(gè)頂點(diǎn)GVI;for(I=0;Ivn;I+)for(j=o;jvn;j+)if(I=j)GAIj=o;elseGAIj=MaxValue;coutvv輸入vvevv條邊vvendl;for(k=1;kv=e;k+)cinIjw;GA

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

9、nt型與char型的替換上不知道用什么函數(shù)實(shí)現(xiàn)；2設(shè)計(jì)體會(huì)對(duì)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ì)第一次使用本程序的人會(huì)很迷茫。3時(shí)間空間復(fù)雜度的計(jì)算利用算法求解最短路徑時(shí)，求每一對(duì)頂點(diǎn)之間的最短路徑的一種方法是反復(fù)

10、執(zhí)行次算法每次執(zhí)行以一個(gè)頂點(diǎn)為源點(diǎn)求得從該頂點(diǎn)到其它各頂點(diǎn)的最短路徑其時(shí)間復(fù)雜度為。其空間的復(fù)雜度為o（n）。五、用戶使用說明本程序主要是用來計(jì)算從某一點(diǎn)到其他各點(diǎn)的最短路徑長度，第一次使用可能會(huì)有點(diǎn)迷茫，但是它卻是本人兩周來的血汗，如有不便請(qǐng)?jiān)?。下面描述該使用方法：程序?huì)在一開始讓用戶輸入結(jié)點(diǎn)數(shù)，線路數(shù)，然后輸入相關(guān)結(jié)點(diǎn)信息，有城市名字（只能使用英文名稱），線路長度，起點(diǎn)城市，終點(diǎn)城市。接下來都由計(jì)算機(jī)完成。結(jié)果會(huì)輸出源點(diǎn)到各城市間的長度。六、測(cè)試結(jié)果輸入數(shù)據(jù)：輸入城市數(shù)為：4輸入城市線路為：4然后輸入城市信息（這里每個(gè)數(shù)字彳弋表1A地2B地3C地4D地）:輸入第一個(gè)城市信息：1輸入第一個(gè)

11、城市信息：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：99F面是結(jié)果截圖:F直每個(gè)數(shù)字代表一個(gè)城市，請(qǐng)輸入相應(yīng)的代碼，第一個(gè)輸入的是出發(fā)地I-7.Jrre二.右亠134-4:也也必自心息息息BitHf:4曙B:乍乍朋乍也也鞋煨讀；rGj入入入一皆釘干謁點(diǎn)點(diǎn)65X?nABC不的的的葩一一一:0一_-r7+-.一thmir藥勻0一5555迪迪迪g*C:DocuentsandSetting

12、suserJ面YDetmgAhs!.eze謝謝使用加R路徑查訂系統(tǒng)，如果想退已請(qǐng)輸入，護(hù),任意犍繼續(xù):七、參考書目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版。八、附錄：帶注釋的源程序*/*/*用Dijkstra算法求出有向圖中某個(gè)源點(diǎn)到其他各頂點(diǎn)的最短路徑長度*/*/*/*/*#includevstdio.h#includevmalloc.h

13、#includeviostream.h#includevstdlib.h#defineINF32767#defineMAXVEX100#defineMAX12structvertexintnum;intdata;；typedefstructgraphintn;inte;structvertexvexsMAXVEX;頂點(diǎn)編號(hào)頂點(diǎn)的信息頂點(diǎn)類型圖中頂點(diǎn)的個(gè)數(shù)和邊的個(gè)數(shù)頂點(diǎn)集合圖的鄰接矩陣類型通過用戶交互產(chǎn)生一個(gè)有向圖的鄰接矩陣對(duì)圖的所有信息進(jìn)行逐步輸入intedgesMAXVEXMAXVEX;邊的集合AdjMaxix;AdjMaxixcreatmgraph()inti,j,k,w,n,e;intb

14、,t;AdjMaxixadj;coutvv輸入城市數(shù):;cinn;while(nMAX|nvO)coutvv城市個(gè)數(shù)不正確!請(qǐng)重新輸入!vvendl;cinn;coutvv輸入城市線路數(shù):；cine;adj.n=n;adj.e=e;coutvv輸入城市信息:n;for(i=0;ivn;i+)coutvv第vvi+1vv個(gè)城市的信息:；cinadj.vexsi.data;adj.vexsi.num=i;for(i=0;ivn;i+)for(j=0;jvn;j+)adj.edgesij=0;for(k=0;kve;k+)coutvv第vvk+1vv條線路:vvendl;coutvv起點(diǎn):；cinb

15、;coutvv終點(diǎn):；cint;coutvv線路長度為(Km):;cinw;i=0;while(ivn&adj.vexsi.data!=b)i+;if(i=n)coutvv輸入的起點(diǎn)城市不存在!n;abort();j=0;while(jvn&adj.vexsj.data!=t)j+;if(j=n)coutvv輸入的終點(diǎn)不存在!n;abort();adj.edgesij=w;return(adj);voiddispmgraph(AdjMaxixadj)/用于輸出一個(gè)有向圖的鄰接矩陣inti,j,n,e;n=adj.n;e=adj.e;coutvv輸出線路的矩陣表示:vvendl;coutvv;f

16、or(i=-1;ivn;i+)printf(%6d,i);printf(n);coutvvendl;for(i=0;ivn;i+)printf(%6d,i);for(j=0;jvn;j+)if(adj.edgesij=O)printf(%6s,“)；elseprintf(%6d,adj.edgesij);coutvvendl;voidppath(intpath,inti,intvO)intk;k=pathi;if(k=vO)return;ppath(path,k,vO);printf(%d,k);voidDisPath(intdist,intpath,ints,intn,intvO)inti;

17、printf(path:);for(i=O;ivn;i+)printf(%3d,pathi);printf(n);for(i=O;ivn;i+)if(si=1&i!=vO)用path計(jì)算最短路徑輸出path值用于輸出最短路徑和路徑長度printf（從4到4的最短路徑為:,vO,i）;printf(%d,vO);ppath(path,i,vO);printf(%dn,i);elseprintf（從4到4不存在路徑n,vO,i）;voidDijkstra(AdjMaxixg,intvO)intdistMAXVEX,pathMAXVEX;intsMAXVEX;intmindis,i,j,u,n=g.

18、n;for(i=0;in;i+)disti=g.edgesvOi;si=0;if(g.edgesvOivINF)pathi=v0;elsepathi=-1;svO=1;pathvO=O;for(i=0;ivn;i+)mindis=INF;u=-1;距離初始化s置空路徑初始化源點(diǎn)編號(hào)vO放入s中循環(huán)直到所有頂點(diǎn)的最短路徑都求出選取不在s中且具有最小距離的頂點(diǎn)ufor(j=0;jvn;j+)if(sj=O&distjvmindis)u=j;mindis=distj;su=1;頂點(diǎn)u加入s中for(j=O;jvn;j+)修改不在s中的頂點(diǎn)的距離if(sj=0)if(g.edgesujvINF&distu+g.edgesujvdistj)distj=distu+g.edgesuj;pathj=u;printf(輸出最短路徑:n);DisPath(dist,path,s,n,v0);voidchange(intnum)switch(num)case1:printf(A地);break;case2:printf(B地);break;case3:printf(C地);b