c++課設(shè)報(bào)告基于Dijkstra算法的最短路徑問(wèn)題求解1

課程設(shè)計(jì)任務(wù)書(shū)學(xué)院學(xué)生姓名設(shè)計(jì)題目?jī)?nèi)容及要求：學(xué)院學(xué)生姓名設(shè)計(jì)題目?jī)?nèi)容及要求：***學(xué)號(hào)*********基于Dijkstra算法的最短路徑問(wèn)題求解進(jìn)行類(lèi)的設(shè)計(jì)與實(shí)現(xiàn)，解決最短路徑問(wèn)題。具體要求如下：(1)采用圖的鄰接矩陣或鄰接表實(shí)現(xiàn)最短路徑問(wèn)題中圖的存儲(chǔ)；(2)采用Dijkstra算法求從某個(gè)源點(diǎn)到其余各頂點(diǎn)的最短路徑；(3)將上述功能作為類(lèi)的成員函數(shù)實(shí)現(xiàn)，編寫(xiě)主函數(shù)測(cè)試上述功能進(jìn)度安排：第17周：分析題目，查閱課題相關(guān)資料，進(jìn)行類(lèi)設(shè)計(jì)、算法設(shè)計(jì)；第18周：程序的設(shè)計(jì)、調(diào)試與實(shí)現(xiàn)；第19周：程序測(cè)試與分析，撰寫(xiě)課程設(shè)計(jì)報(bào)告，進(jìn)行答辯驗(yàn)收。指導(dǎo)教師(簽字)：學(xué)院院長(zhǎng)(簽字)年月日年月日TOC\o"1-5"\h\z1需求分析-1-2算法基本原理-2-3類(lèi)設(shè)計(jì)-3-4詳細(xì)設(shè)計(jì)-5-類(lèi)的接口設(shè)計(jì)-5-類(lèi)的實(shí)現(xiàn)-5-主函數(shù)設(shè)計(jì)-7-5DOS界面程序運(yùn)行結(jié)果及分析-8-程序運(yùn)行結(jié)果-8-運(yùn)行結(jié)果分析-9-6基于MFC的圖形界面程序開(kāi)發(fā)-9-基于MFC的圖形界面程序設(shè)計(jì)-10-程序測(cè)試-13MFC程序編寫(xiě)總結(jié)-14-7參考文獻(xiàn)-15-1需求分析Dijkstra算法是由荷蘭計(jì)算機(jī)科學(xué)家艾茲格?迪科斯徹發(fā)現(xiàn)的。算法解決的是有向圖中最短路徑問(wèn)題。舉例來(lái)說(shuō)，如果圖中的頂點(diǎn)表示城市，而邊上的權(quán)重表示著城市間開(kāi)車(chē)行經(jīng)的距離。Dijkstra算法可以用來(lái)找到兩個(gè)城市之間的最短路徑。Dijkstra算法的輸入包含了一個(gè)有權(quán)重的有向圖G,以及G中的一個(gè)來(lái)源頂點(diǎn)S。我們以V表示G中所有頂點(diǎn)的集合。圖中的每一個(gè)邊，都是兩個(gè)頂點(diǎn)所形成的有序元素對(duì)。（u,v）表示從頂點(diǎn)u到v有路徑相連。假設(shè)E為所有邊的集合，而邊的權(quán)重則由權(quán)重函數(shù)w:E-[0,00]定義。因此，w（u,v）就是從頂點(diǎn)u到頂點(diǎn)v的非負(fù)花費(fèi)值（cost）。邊的花費(fèi)可以想像成兩個(gè)頂點(diǎn)之間的距離。任兩點(diǎn)間路徑的花費(fèi)值，就是該路徑上所有邊的花費(fèi)值總和。已知有V中有頂點(diǎn)s及t,Dijkstra算法可以找到s到t的最低花費(fèi)路徑（i.e.最短路徑）。這個(gè)算法也可以在一個(gè)圖中，找到從一個(gè)頂點(diǎn)s到任何其他頂點(diǎn)的最短路徑。|1.如果將交通網(wǎng)絡(luò)化成帶權(quán)圖，假如用頂點(diǎn)表示城市，邊表示公路段，則由這些頂點(diǎn)和邊組成的圖可表示溝通個(gè)城市的公路圖，邊的權(quán)用以表示兩個(gè)城市之間的距離或者表示走過(guò)這段公路所需要的時(shí)間或通過(guò)這段路的難易程度等。作為司機(jī)和乘汽車(chē)的人，自然會(huì)關(guān)心如下兩個(gè)問(wèn)題：（1）從甲地到乙地是否有公路？（2）從甲地到乙地有幾條公路，哪條公路最短或花費(fèi)的代價(jià)最?。窟@就是我們要討論的最短路徑問(wèn)題。.迪杰斯特拉提出的一個(gè)求最短路徑的算法。其基本思想是：按路徑長(zhǎng)度遞增的順序，逐個(gè)產(chǎn)生各最短路徑。.首先引進(jìn)輔助向量dist口，它的每一個(gè)分量dist[i]表示已經(jīng)找到的且從源點(diǎn)vo到每一個(gè)終點(diǎn)vi的當(dāng)前最短路徑長(zhǎng)度。它的初態(tài)為：如果從vo到vi有弧，則dist[i]為弧的權(quán)值；否則dist[i]為*。其中，長(zhǎng)度為dist[j]=min{dist[i]|viWV}的路徑是從v0出發(fā)的長(zhǎng)度最短的一條最短路徑，此2算法基本原理根據(jù)以上分析，可以得到如下描述的算法：①假設(shè)用帶權(quán)的鄰接矩陣arce[i][j]來(lái)表示帶權(quán)有向圖，arce[i][j]表示弧＜Vi,vj＞上的權(quán)值。若＜Vi,vj＞不存在，則置arce[i][j]為“（在計(jì)算機(jī)上可用允許的最大值代替）。S為已找到的從V0出發(fā)的最短路徑的終點(diǎn)的集合，它的初始狀態(tài)為空集。那么，從V0出發(fā)到圖上其余個(gè)頂點(diǎn)（終點(diǎn)）Vi可能達(dá)到的最短路徑長(zhǎng)度的初值為：dist[i]=arce[LocateVex（G,v0）][i]VieS②選擇vj得dist[j]=min{dist[i]|Vi€V-S}vj就是當(dāng)前求得的一條從vo出發(fā)的最短路徑的終點(diǎn)。令S=SU{j}o③修改從vo出發(fā)到集合V-S上任一頂點(diǎn)Vk可達(dá)的最短頂點(diǎn)長(zhǎng)度。如果dist[j]+arce[j][k]＜dist[k]則修改dist[k]為dist[k]=dist[j]+arce[j][k]④重復(fù)操作②、③共n-1次。由此求得從vo到圖上其余各頂點(diǎn)的最短路徑是依路徑長(zhǎng)度遞增的序列。用Dijkstra算法求有向圖G的V。頂點(diǎn)到其余頂點(diǎn)v的最短路徑P[v]及其帶權(quán)長(zhǎng)度D[v]。這個(gè)算法是通過(guò)為每個(gè)頂點(diǎn)V保留目前為止所找到的從s到V的最短路徑來(lái)工作的。初始時(shí)，源點(diǎn)s的路徑長(zhǎng)度值被賦為0（d[s]=0）,同時(shí)把所有其他頂點(diǎn)的路徑長(zhǎng)度設(shè)為無(wú)窮大，即表示我們不知道任何通向這些頂點(diǎn)的路徑（對(duì)于V中所有頂點(diǎn)v除s外d[v]=°°）。當(dāng)算法結(jié)束時(shí)，d[v]中儲(chǔ)存的便是從s到v的最短路徑，或者是無(wú)窮大（如果路徑不存在的話）。Dijstra算法的基礎(chǔ)操作是邊的拓展：如果存在一條從u到v的邊，那么從s到v的最短路徑可以通過(guò)將邊(u,v)添加到s到u的尾部來(lái)拓展。這條路徑的長(zhǎng)度是d[u]+w(u,v)。如果這個(gè)值比目前已知的d[v]的值要小，我們可以用新值來(lái)替代當(dāng)前d[v]中的值。拓展邊的操作一直執(zhí)行到所有的d[v]都代表從s到v最短路徑的花費(fèi)。這個(gè)算法經(jīng)過(guò)適當(dāng)?shù)慕M織因而當(dāng)d[u]達(dá)到它最終的值的時(shí)候，每條邊(u,v)都只被拓展一次。算法維護(hù)兩個(gè)頂點(diǎn)集S和Qo集合S保留了我們已知的所有d[v]的值已經(jīng)是最短路徑的值頂點(diǎn)，而集合Q則保留其他所有頂點(diǎn)。集合S初始狀態(tài)為空，而后每一步都有一個(gè)頂點(diǎn)從Q移動(dòng)到So這個(gè)被選擇的頂點(diǎn)是Q中擁有最小的d[u]值的頂點(diǎn)。當(dāng)一個(gè)頂點(diǎn)u從Q中轉(zhuǎn)移到了S中，算法對(duì)每條外接邊(u,v)進(jìn)行拓展。Dijkstra(G,D,s){〃用Dijkstra算法求有向網(wǎng)G的源點(diǎn)s到各頂點(diǎn)的最短路徑長(zhǎng)度//以下是初始化操作S={s};D[s]=0;〃設(shè)置初始的紅點(diǎn)集及最短距離for(alliGV-S)do〃對(duì)藍(lán)點(diǎn)集中每個(gè)頂點(diǎn)iD[i]=G[s][i];//設(shè)置i初始的估計(jì)距離為w<s,i>〃以下是擴(kuò)充紅點(diǎn)集for(i=0;i<n-1;i++)do{//最多擴(kuò)充n-1個(gè)藍(lán)點(diǎn)到紅點(diǎn)集D[k]=min{D[i]:alliV-S};〃在當(dāng)前藍(lán)點(diǎn)集中選估計(jì)距離最小的頂點(diǎn)kif(D[k]等于oo)return;〃藍(lán)點(diǎn)集中所有藍(lán)點(diǎn)的估計(jì)距離均為00時(shí)，//表示這些頂點(diǎn)的最短路徑不存在。S=SU{k};〃將藍(lán)點(diǎn)k涂紅后擴(kuò)充到紅點(diǎn)集for(allj€V-S)do//調(diào)整剩余籃點(diǎn)的估計(jì)距離if(D[j]>D[k]+G[k][j])〃新紅點(diǎn)k使原D[j]值變小時(shí)，用新路徑的長(zhǎng)度修改D[j],〃使j離s更近。D[j]=D[k]+G[k][j];一}}3類(lèi)設(shè)計(jì)從上面的算法分析可以看到，根據(jù)算法設(shè)計(jì)了類(lèi)classSPFA,public:intn;表示圖里面的點(diǎn)數(shù)，public:intpath[MAX][MAX];定義鏈接矩陣最多是1000個(gè)點(diǎn)，public:in，dis[MAX];定義源L4其伊點(diǎn)伸呼離，}puglic:）ntsrc;定義源點(diǎn),boolused[MAX]={false};定義點(diǎn)是否訪問(wèn)過(guò)了，初始化為未訪問(wèn)，初始化一下到各個(gè)點(diǎn)的距離，如果從k點(diǎn)走到j(luò)點(diǎn)的路很比原來(lái)的要短，那么更新，采用圖的鄰接矩陣或鄰接表實(shí)沙岬豆路徑問(wèn)題中圖的「呵，采用Dijkstra算法求從某個(gè)源點(diǎn)到其余各頂點(diǎn)的最短路徑。第一步先取WV10意即V1到V1的粘部為0,而Tvj是對(duì)Tvj所賦的初值。第二步利用Wv1已知，根據(jù)minTvj,Wviwij對(duì)Tvj進(jìn)行修正。第三步對(duì)所有修正后的Tvj求出其最小者Tvk。其對(duì)應(yīng)的點(diǎn)vk是v1所能一步到達(dá)的點(diǎn)vj中最近的一個(gè)，由于所有iWu,0o因此任何從其它點(diǎn)vj中轉(zhuǎn)而到達(dá)vk的通路上的距離都大于v1直接到vk的距離Tvk，因此Tvk就是v1到vk中葉短[離）,所以在算法中令WvkTvk并從s中刪二去vk,若k=n則WvkWvn就是v1到vn的最短路線，計(jì)算結(jié)束。否則令vivk回到第二步，繼續(xù)運(yùn)算，直到k=n為止。這樣每一次迭代，得到重復(fù)上述過(guò)程直到.v1到一點(diǎn)vk的最短距離,vkvnoFloyd算法的基本原理和實(shí)現(xiàn)方法為：如果一個(gè)矩陣Ddij其中dij0表示i與j間的距離，若i與j間無(wú)路可通，則dij為無(wú)窮大。i與j閣的最短距離存在經(jīng)過(guò)i與■Mij間的k和不經(jīng)過(guò)k兩種情況，所以可以令k1,2,3,,n,n（n為節(jié)點(diǎn)數(shù)）。檢查dj與dikdkj的值，在此，dik與dkj分別為目前所知的i到k與k到j(luò)的最短距離，因此,就是i到經(jīng)過(guò)k的最短距離。所以若有i出發(fā)dikdkjj:，…dijdikdkj，就表示從經(jīng)k再到j(luò)的距離要比原來(lái)的i到j(luò)距離短，自然把i到j(luò)的dij重寫(xiě)成dikdkj。每當(dāng)一fk搜索完，dij就是目前i到j(luò)的最短距離。重復(fù)這一過(guò)程，最后當(dāng)查完所有k時(shí),dij就為i到j(luò)的最短距離。4詳細(xì)設(shè)計(jì)首先，這個(gè)程序定義了一個(gè)類(lèi)classSPFA,通過(guò)此類(lèi)定義鏈接矩陣，采用圖的鄰接矩陣或鄰接表實(shí)現(xiàn)最短路徑問(wèn)題中圖的存儲(chǔ)，然后通過(guò)主函數(shù)main調(diào)用class來(lái)實(shí)現(xiàn)，采用Dijkstra算法求從某個(gè)源點(diǎn)到其余各頂點(diǎn)的最短路徑。類(lèi)的接口設(shè)計(jì)#include<iostream>usingnamespacestd;constintMAX=1000;constintINF=1000000000;classSPFA{public:intn;〃表示圖里面的點(diǎn)數(shù)public:intpath[MAX][MAX];//定義鏈接矩陣最多是1000個(gè)點(diǎn)public:intdis[MAX];//定義源點(diǎn)到其他點(diǎn)的距離public:intsrc;//定義源點(diǎn)經(jīng)過(guò)公有派生，在類(lèi)的接口定義了圖里面的點(diǎn)數(shù)，定義鏈接矩陣最多是1000個(gè)點(diǎn)，定義源點(diǎn)到其他點(diǎn)的距離，定義源點(diǎn)經(jīng)過(guò)公有派生，這些變量intn,intpath[MAX][MAX],intdis[MAX],intsrc都是public型。類(lèi)的實(shí)現(xiàn)public:voidCal()inti,j,k;boolused[MAX]={false};//定義點(diǎn)是否訪問(wèn)過(guò)了，初始化為未訪問(wèn)for(i=0;i<n;i++)//初始化一下到各個(gè)點(diǎn)的距離{dis[i]=path[src][i];)dis[src]=0;intmin_=INF;for(i=0;i<n;i++)(k=-1;min_=INF;for(j=0;j<n;j++)(if(dis[j]<min_&&!used[j])(min_=dis[j];k=j;))if(k==-1)//已經(jīng)找不到有路可走的點(diǎn)(return;)used[k]=true;for(j=0;j<n;j++)(if(!used[j]&&dis[j]>min_+path[k][j])//如果從k點(diǎn)走到j(luò)點(diǎn)的路很比原來(lái)的要短，那么更新(dis[j]=min_+path[k][j];)))));在類(lèi)的成員函數(shù)實(shí)現(xiàn)過(guò)程中，設(shè)計(jì)了幾個(gè)循環(huán)語(yǔ)句，和判斷語(yǔ)句，定義點(diǎn)是否訪問(wèn)過(guò)了，初始化為未訪問(wèn)，初始化一下到各個(gè)點(diǎn)的距離，已經(jīng)找不到有路可走的點(diǎn)，if(!used[j]&&dis[j]>min_+path[k][j])//如果從k點(diǎn)走到j(luò)點(diǎn)的路很比原來(lái)的要短，那么更新主函數(shù)設(shè)計(jì)intmain(){//按照下面的數(shù)據(jù)格式輸入,-1表示沒(méi)有路，自己到自己是0/*30-1-130-134030100130-1340301230-1340*/SPFA*a=newSPFA();cout<<”請(qǐng)輸入點(diǎn)數(shù)：”；cin>>a->n;inti,j;for(i=0;i<a->n;i++)(for(j=0;j<a->n;j++){cin>>a->path[i][j];if(a->path[i][j]==-1)(a->path[i][j]=INF;)))a->src=0;//源點(diǎn)暫時(shí)定為0,你自己改吧a->Cal();for(i=0;i<a->n;i++)(cout<<"dis[i]="<<i<<a->dis[i]<<endl;)return0;)在程序的主函數(shù)部分，可以顯示"請(qǐng)輸入點(diǎn)數(shù)："輸入一個(gè)鄰接矩陣，a->src=0;//源點(diǎn)暫時(shí)定為0,然后通過(guò)循環(huán)語(yǔ)句，調(diào)用類(lèi)中的函數(shù)，算出最短路徑。5DOS界面程序運(yùn)行結(jié)果及分析程序運(yùn)行結(jié)果程序運(yùn)行結(jié)果如圖2所示?！癕S“MSIHhrrDmwrrii方程組類(lèi)，并通過(guò)圖形界面的輸入輸出改造來(lái)完成J||1^I耐6」基于mfc器髓微r設(shè)計(jì)(1)界面設(shè)計(jì)先在VC掖I如rtMFCAppWizard(exe)工程，名稱(chēng)旃5G啪網(wǎng)LineGUI向?qū)У腟tep1"I印普魄1&8"1bAnw/iUbjinw191,即建立基于對(duì)話框崢用栓厚尸如下圖,并在4-54喀立MFCAppWizard(exe)工程MtJUM圖5建立基于對(duì)話框的應(yīng)用程序一rIt*nt*，rt.'nr*fhjit1A.?MJt*r*1i.將對(duì)話框資源中的默認(rèn)對(duì)話框利用工具箱改造成如下界面，如圖’6所示-10-BickIHod》I[ItitkCtiKfi1＜；?Ujiyh(lift-，(2)代碼設(shè)埠溫肌為了能夠?qū)?duì)話框標(biāo)上的控件能夠與代碼聯(lián)系起來(lái),VH甫函詢(xún)24個(gè)EditBox控件建立MemberVariablesIlkMemberVariables溫ikh/imUM叫如榔；(2)代碼設(shè)埠溫肌為了能夠?qū)?duì)話框標(biāo)上的控件能夠與代碼聯(lián)系起來(lái),VH甫函詢(xún)24個(gè)EditBox控件建立MemberVariablesIlkMemberVariables溫ikh/imUM叫如榔；按Ctrl+w犍進(jìn)入MFCClassWizard界面，選擇Im也咕“7所示。hf川11I，?【”1〔研?\\IUHMilIfkii圖7成員變量設(shè)置界面通過(guò)該界面設(shè)置與24個(gè)EditBox控件對(duì)應(yīng)的成員變量，耳體如表2所示?？丶蘒D表2控件基本信息成員變量類(lèi)型?it；(I成員變量名稱(chēng)m_1~m_2m_2~m_3m_3?m_4m_1~m_2m_2~m_3m_3?m_4IDC_EDIT_b0~IDC_EDIT_b3doubleIDC_EDIT_X0?IDC_EDIT_X3double下面是編寫(xiě)代碼的重要階段，可以借鑒在設(shè)計(jì)基于DOS界面的控制臺(tái)應(yīng)用程序的代碼，并將其作必要的改寫(xiě)，具體改寫(xiě)的步驟與內(nèi)容如下。①將class文件，重新命名為class.h,并將其加入MFC工程。②修改class文件具體包括：將顯示矩陣PrintM()函數(shù)和顯示方程PrintL()函數(shù)注釋掉，因?yàn)樵趫D形界面的程序上已經(jīng)不需要遷個(gè)函數(shù)力擔(dān)輸出功能了;~?1將輸出方程組的解ShowX()函數(shù)加入?yún)?shù)doublex[]變成ShowX(d，ublex[]),以實(shí)現(xiàn)將所求的解輸出至參數(shù)x中，并I終完成在對(duì)話框界面,的顯示；將全選主元高斯法求解函數(shù)Solve()中的兩處,ut語(yǔ)句去掉，因?yàn)椤缎枰膊荒軌蚴褂脋cout流實(shí)現(xiàn)輸mo'?4③在對(duì)話框類(lèi)的實(shí)現(xiàn)文件GuassLineGUIDlg.cpp中加入#include"Linequ.h",以實(shí)現(xiàn)在該文件中可使用Linequ類(lèi)。④在GuassLineGUIDlg.cpp文件中加入以下全局變量的定義，以實(shí)現(xiàn)GuassLineGUIDlg類(lèi)和Linequ類(lèi)之間的通信，具體代碼如下：doublea[]=〃系數(shù)矩陣(0.2368,0.2471,0.2568,1.2671,0.1968,0.2071,1.2168,0.2271,0.1581,1.1675,0.1768,0.1871,1.1161,0.1254,0.1397,0.1490};doubleb[4]={1.8471,1.7471,1.6471,1.5471};//方程右端項(xiàng)double*X;〃存放方程組的解⑤編寫(xiě)讀入數(shù)據(jù)按鈕的消息處理函數(shù)，實(shí)現(xiàn)將矩陣和右端項(xiàng)的數(shù)據(jù)刷新到界面上，具體代碼如下：voidCGuassLineGUIDlg::OnBUTTONRead(){//TODO:Addyourcontrolnotificationhandlercodeherem_A00=a[0];m_A01=a[1];m_A02=a[2];m_A03=a[3];m_A10=a[5];m_A11=a[6];m_A12=a[7];m_A13=a[8];m_A20=a[9];m_A21=a[10];m_A22=a[11];m_A23=a[12];m_A30=a[13];m_A31=a[14];m_A32=a[15];m_A33=a[16];m_b0=b[0];m_b1=b[1];m_b2=b[2];m_b3=b[3];UpdateData(FALSE);}⑥編寫(xiě)計(jì)算求解按鈕的消息處理函數(shù)，實(shí)現(xiàn)將方程求解，具體代碼如下：voidCGuassLineGUIDlg::OnButtonCalc(){//TODO:AddyourcontrolnotificationhandlercodehereLinequequ1(4);//定義一個(gè)四元方程組對(duì)象equ1.SetLinequ(a,b);//設(shè)置方程組X=newdouble[4];if(equ1.Solve())//求解方程組equl.ShowX(X);//輸出方程組的解m_X0=X[0];m_X1=X[1];m_X2=X[2];m_X3=X[3];UpdateData(FALSE);)elseMessageBox("求解失敗");〃求解失敗)⑦退出按鈕比較簡(jiǎn)單，代碼如下：voidCGuassLineGUIDlg::OnBUTTONExit()(//TODO:Addyourcontrolnotification