c課設(shè)報告基于Dijkstra算法的最短路徑問題求解_第1頁
c課設(shè)報告基于Dijkstra算法的最短路徑問題求解_第2頁
c課設(shè)報告基于Dijkstra算法的最短路徑問題求解_第3頁
c課設(shè)報告基于Dijkstra算法的最短路徑問題求解_第4頁
c課設(shè)報告基于Dijkstra算法的最短路徑問題求解_第5頁
已閱讀5頁,還剩9頁未讀, 繼續(xù)免費閱讀

下載本文檔

版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進行舉報或認領(lǐng)

文檔簡介

1、-. z.課 程 設(shè) 計 任 務(wù) 書學(xué)院信息科學(xué)與工程專業(yè)通信工程學(xué)生*設(shè)計題目基于Dijkstra算法的最短路徑問題求解容及要求:進展類的設(shè)計與實現(xiàn),解決最短路徑問題。具體要求如下:采用圖的鄰接矩陣或鄰接表實現(xiàn)最短路徑問題中圖的存儲;采用Dijkstra算法求從*個源點到其余各頂點的最短路徑;將上述功能作為類的成員函數(shù)實現(xiàn),編寫主函數(shù)測試上述功能。進度安排:第17周:分析題目,查閱課題相關(guān)資料,進展類設(shè)計、算法設(shè)計;第18周:程序的設(shè)計、調(diào)試與實現(xiàn);第19周:程序測試與分析,撰寫課程設(shè)計報告,進展辯論驗收。指導(dǎo)教師簽字:年 月 日學(xué)院院長簽字年 月 日目 錄 TOC o 1-3 h z u

2、HYPERLINK l _Toc2168441001 需求分析 PAGEREF _Toc216844100 h - 1 -HYPERLINK l _Toc2168441012 算法根本原理 PAGEREF _Toc216844101 h - 1 -HYPERLINK l _Toc2168441023 類設(shè)計 PAGEREF _Toc216844102 h - 2 -HYPERLINK l _Toc2168441034 詳細設(shè)計 PAGEREF _Toc216844103 h - 3 -HYPERLINK l _Toc2168441044.1 類的接口設(shè)計 PAGEREF _Toc2168441

3、04 h - 3 -HYPERLINK l _Toc2168441054.2 類的實現(xiàn) PAGEREF _Toc216844105 h - 5 -HYPERLINK l _Toc2168441064.3 主函數(shù)設(shè)計 PAGEREF _Toc216844106 h - 10 -HYPERLINK l _Toc2168441075 DOS界面程序運行結(jié)果及分析 PAGEREF _Toc216844107 h - 11 -HYPERLINK l _Toc2168441085.1 程序運行結(jié)果 PAGEREF _Toc216844108 h - 11 -HYPERLINK l _Toc21684410

4、95.2運行結(jié)果分析 PAGEREF _Toc216844109 h - 12 -HYPERLINK l _Toc2168441106 基于MFC的圖形界面程序開發(fā) PAGEREF _Toc216844110 h - 13 -HYPERLINK l _Toc2168441116.1 基于MFC的圖形界面程序設(shè)計 PAGEREF _Toc216844111 h - 13 -HYPERLINK l _Toc2168441126.2 程序測試 PAGEREF _Toc216844112 h - 15-HYPERLINK l _Toc2168441136.3 MFC程序編寫總結(jié) PAGEREF _To

5、c216844113 h - 17 -HYPERLINK l _Toc2168441147 參考文獻 PAGEREF _Toc216844114 h - 17. z.1 需求分析Dijkstra算法是由荷蘭計算機科學(xué)家艾茲格迪科斯徹發(fā)現(xiàn)的。算法解決的是有向圖中最短路徑問題。舉例來說,如果圖中的頂點表示城市,而邊上的權(quán)重表示著城市間開車行經(jīng)的距離。 Dijkstra算法可以用來找到兩個城市之間的最短路徑。Dijkstra算法的輸入包含了一個有權(quán)重的有向圖G,以及G中的一個來源頂點S。 我們以V表示G中所有頂點的集合。圖中的每一個邊,都是兩個頂點所形成的有序元素對。(u,v)表示從頂點u到v有路徑

6、相連。 假設(shè)E為所有邊的集合,而邊的權(quán)重則由權(quán)重函數(shù)w:E 0, 定義。 因此,w(u,v)就是從頂點u到頂點v的非負花費值(cost)。 邊的花費可以想像成兩個頂點之間的距離。任兩點間路徑的花費值,就是該路徑上所有邊的花費值總和。 有V中有頂點s及t,Dijkstra算法可以找到s到t的最低花費路徑(i.e. 最短路徑)。 這個算法也可以在一個圖中,找到從一個頂點s到任何其他頂點的最短路徑。1如果將交通網(wǎng)絡(luò)化成帶權(quán)圖,假設(shè)用頂點表示城市,邊表示公路段,則由這些頂點和邊組成的圖可表示溝通個城市的公路圖,邊的權(quán)用以表示兩個城市之間的距離或者表示走過這段公路所需要的時間或通過這段路的難易程度等。作

7、為司機和乘汽車的人,自然會關(guān)心如下兩個問題:1從甲地到乙地是否有公路?2從甲地到乙地有幾條公路,哪條公路最短或花費的代價最???這就是我們要討論的最短路徑問題。2.迪杰斯特拉提出的一個求最短路徑的算法。其根本思想是:按路徑長度遞增的順序,逐個產(chǎn)生各最短路徑。 3首先引進輔助向量dist,它的每一個分量disti表示已經(jīng)找到的且從源點到每一個終點的當(dāng)前最短路徑長度。它的初態(tài)為:如果從到有弧,則disti為弧的權(quán)值;否則disti為。其中,長度為distj=mindisti|V的路徑是從出發(fā)的長度最短的一條最短路徑,此路徑為,。2 算法根本原理根據(jù)以上分析,可以得到如下描述的算法:假設(shè)用帶權(quán)的鄰接矩

8、陣arceij來表示帶權(quán)有向圖,arceij表示弧上的權(quán)值。假設(shè)不存在,則置arceij為在計算機上可用允許的最大值代替。S為已找到的從出發(fā)的最短路徑的終點的集合,它的初始狀態(tài)為空集。則,從出發(fā)到圖上其余個頂點終點可能到達的最短路徑長度的初值為: disti=arceLocate Ve*(G,)iS選擇得 distj=mindisti|V-S就是當(dāng)前求得的一條從出發(fā)的最短路徑的終點。令S=Sj。修改從出發(fā)到集合V-S上任一頂點可達的最短頂點長度。如果 distj+arcejkdistk則修改distk為 distk=distj+arcejk重復(fù)操作、共n-1次。由此求得從到圖上其余各頂點的最短

9、路徑是依路徑長度遞增的序列。用Dijkstra算法求有向圖G的頂點到其余頂點v的最短路徑Pv及其帶權(quán)長度Dv。 這個算法是通過為每個頂點v保存目前為止所找到的從s到v的最短路徑來工作的。初始時,源點s的路徑長度值被賦為0ds=0, 同時把所有其他頂點的路徑長度設(shè)為無窮大,即表示我們不知道任何通向這些頂點的路徑對于V中所有頂點v除s外dv= 。當(dāng)算法完畢時,dv中儲存的便是從s到v的最短路徑,或者是無窮大如果路徑不存在的話。 Dijstra算法的根底操作是邊的拓展:如果存在一條從u到v的邊,則從s到v的最短路徑可以通過將邊(u,v)添加到s到u的尾部來拓展。這條路徑的長度是du+w(u,v)。如

10、果這個值比目前的dv的值要小,我們可以用新值來替代當(dāng)前dv中的值。拓展邊的操作一直執(zhí)行到所有的dv都代表從s到v最短路徑的花費。這個算法經(jīng)過適當(dāng)?shù)慕M織因而當(dāng)du到達它最終的值的時候,每條邊(u,v)都只被拓展一次。算法維護兩個頂點集S和Q。集合S保存了我們的所有dv的值已經(jīng)是最短路徑的值頂點,而集合Q則保存其他所有頂點。集合S初始狀態(tài)為空,而后每一步都有一個頂點從Q移動到S。這個被選擇的頂點是Q中擁有最小的du值的頂點。當(dāng)一個頂點u從Q中轉(zhuǎn)移到了S中,算法對每條外接邊(u,v)進展拓展。Dijkstra(G,D,s) /用Dijkstra算法求有向網(wǎng)G的源點s到各頂點的最短路徑長度 /以下是初

11、始化操作 S=s;Ds=0; /設(shè)置初始的紅點集及最短距離 for( all i V-S )do /對藍點集中每個頂點i Di=Gsi; /設(shè)置i初始的估計距離為w /以下是擴大紅點集 for(i=0;iDk+Gkj) /新紅點k使原Dj值變小時,用新路徑的長度修改Dj, /使j離s更近。 Dj=Dk+Gkj; 3 類設(shè)計從上面的算法分析可以看到,根據(jù)算法設(shè)計了類class SPFA,public: int n;表示圖里面的點數(shù),public: int pathMA*MA*;定義矩陣最多是1000個點,public: int disMA*;定義源點到其他點的距離,public: int src

12、;定義源點,bool usedMA*=false;定義點是否訪問過了,初始化為未訪問,初始化一下到各個點的距離,如果從k點走到j(luò)點的路很比原來的要短,則更新,采用圖的鄰接矩陣或鄰接表實現(xiàn)最短路徑問題中圖的存儲,采用Dijkstra算法求從*個源點到其余各頂點的最短路徑。第一步 先取意即到的距離為0,而是對所賦的初值。第二步 利用,根據(jù)對進展修正。第三步 對所有修正后的求出其最小者。其對應(yīng)的點是所能一步到達的點中最近的一個,由于所有。因此任何從其它點中轉(zhuǎn)而到達的通路上的距離都大于直接到的距離,因此就是到的最短距離,所以在算法中令并從s中刪去,假設(shè)k=n則就是到的最短路線,計算完畢。否則令回到第二

13、步,繼續(xù)運算,直到k=n為止。這樣每一次迭代,得到到一點的最短距離,重復(fù)上述過程直到。Floyd算法的根本原理和實現(xiàn)方法為:如果一個矩陣其中表示與間的距離,假設(shè)與間無路可通,則為無窮大。與間的最短距離存在經(jīng)過與間的和不經(jīng)過兩種情況,所以可以令,n(n為節(jié)點數(shù))。檢查與的值,在此,與分別為目前所知的到與到的最短距離,因此,就是到經(jīng)過的最短距離。所以,假設(shè)有,就表示從出發(fā)經(jīng)再到的距離要比原來的到距離短,自然把到的重寫成。每當(dāng)一個搜索完,就是目前到的最短距離。重復(fù)這一過程,最后當(dāng)查完所有時,就為到的最短距離。4 詳細設(shè)計首先,這個程序定義了一個類class SPFA,通過此類定義矩陣,采用圖的鄰接矩

14、陣或鄰接表實現(xiàn)最短路徑問題中圖的存儲,然后通過主函數(shù)main調(diào)用class來實現(xiàn),采用Dijkstra算法求從*個源點到其余各頂點的最短路徑。4.1 類的接口設(shè)計#includeusing namespace std;const int MA*=1000;const int INF=1000000000; class SPFApublic: int n;/表示圖里面的點數(shù)public: int pathMA*MA*;/定義矩陣最多是1000個點public: int disMA*;/定義源點到其他點的距離public: int src;/定義源點經(jīng)過公有派生,在類的接口定義了圖里面的點數(shù),定義

15、矩陣最多是1000個點,定義源點到其他點的距離,定義源點經(jīng)過公有派生,這些變量int n,int pathMA*MA*,int disMA*,int src都是public型。4.2 類的實現(xiàn)public:void Cal()int i,j,k;bool usedMA*=false;/定義點是否訪問過了,初始化為未訪問for(i=0;in;i+)/初始化一下到各個點的距離disi=pathsrci;dissrc=0;int min_=INF;for(i=0;in;i+)k=-1;min_=INF;for(j=0;jn;j+)if(disjmin_&!usedj)min_=disj;k=j;if

16、(k=-1)/已經(jīng)找不到有路可走的點return;usedk=true;for(j=0;jmin_+pathkj)/如果從k點走到j(luò)點的路很比原來的要短,則更新disj=min_+pathkj;在類的成員函數(shù)實現(xiàn)過程中,設(shè)計了幾個循環(huán)語句,和判斷語句,定義點是否訪問過了,初始化為未訪問,初始化一下到各個點的距離,已經(jīng)找不到有路可走的點,if(!usedj&disjmin_+pathkj)/如果從k點走到j(luò)點的路很比原來的要短,則更新4.3 主函數(shù)設(shè)計int main()/按照下面的數(shù)據(jù)格式輸入,-1表示沒有路,自己到自己是0/*30 -1 -13 0 -13 4 030 100 13 0 -1

17、3 4 030 1 23 0 -13 4 0*/SPFA* a=new SPFA();couta-n;int i,j;for(i=0;in;i+)for(j=0;jn;j+)cina-pathij;if(a-pathij=-1)a-pathij=INF;a-src=0;/源點暫時定為0,你自己改吧a-Cal();for(i=0;in;i+)coutdisi=idisisrc=0;/源點暫時定為0,然后通過循環(huán)語句,調(diào)用類中的函數(shù),算出最短路徑。5 DOS界面程序運行結(jié)果及分析5.1 程序運行結(jié)果程序運行結(jié)果如圖2所示。圖2 程序運行結(jié)果5.2運行結(jié)果分析整個程序中的矩陣存儲采用的是一維數(shù)組和動

18、態(tài)存分配方式。通過此類定義矩陣,采用圖的鄰接矩陣或鄰接表實現(xiàn)最短路徑問題中圖的存儲,然后通過主函數(shù)main調(diào)用class來實現(xiàn),采用Dijkstra算法求從*個源點到其余各頂點的最短路徑。6 基于MFC的圖形界面程序開發(fā)MFC的圖形界面程序設(shè)計可在上述類設(shè)計的根底上進展改造,MFC的圖形界面程序與DOS界面程序的主要不同點是:MFC圖形界面程序與DOS界面程序的輸入輸出方式不同,DOS界面程序采用字符交互式實現(xiàn)數(shù)據(jù)輸入輸出,主要通過cin,cout等I/O流實現(xiàn),而MFC的圖形程序界面采用標準Windows窗口和控件實現(xiàn)輸入輸出,因此必須在MFC類的框架下參加上面所設(shè)計的矩陣和方程組類,并通過

19、圖形界面的輸入輸出改造來完成。6.1 基于MFC的圖形界面程序設(shè)計1界面設(shè)計首先在VC中建立MFC AppWizard(e*e)工程,名稱為GuassLineGUI,并在向?qū)У腟tep1中選擇Dialog based,即建立基于對話框的應(yīng)用程序,如下列圖45所示。圖4 建立MFC AppWizard(e*e)工程圖5 建立基于對話框的應(yīng)用程序?qū)υ捒蛸Y源中的默認對話框利用工具箱改造成如下界面,如圖6所示。2代碼設(shè)置為了能夠?qū)υ捒蚪缑嫔系目丶軌蚺c代碼聯(lián)系起來,需要為24個Edit Bo*控件建立Member Variables,按Ctrl+w鍵進入MFC ClassWizard界面,選擇Me

20、mber Variables選項卡,可顯示成員變量設(shè)置界面,如圖7所示。圖7 成員變量設(shè)置界面通過該界面設(shè)置與24個Edit Bo*控件對應(yīng)的成員變量,具體如表2所示。表2 控件根本信息控件ID成員變量類型成員變量名稱IDC_EDIT_A00 IDC_EDIT_A33doublem_1m_2IDC_EDIT_b0 IDC_EDIT_b3doublem_2m_3IDC_EDIT_*0 IDC_EDIT_*3doublem_3m_4下面是編寫代碼的重要階段,可以借鑒在設(shè)計基于DOS界面的控制臺應(yīng)用程序的代碼,并將其作必要的改寫,具體改寫的步驟與容如下。將class文件,重新命名為class.h,并

21、將其參加MFC工程。修改class文件具體包括:將顯示矩陣PrintM()函數(shù)和顯示方程PrintL()函數(shù)注釋掉,因為在圖形界面的程序上已經(jīng)不需要連個函數(shù)承當(dāng)輸出功能了;將輸出方程組的解Show*()函數(shù)參加參數(shù)double *變成Show*(double *),以實現(xiàn)將所求的解輸出至參數(shù)*中,并最終完成在對話框界面上的顯示;將全選主元高斯法求解函數(shù)Solve()中的兩處cout語句去掉,因為不需要也不能夠使用cout流實現(xiàn)輸出。在對話框類的實現(xiàn)文件GuassLineGUIDlg.cpp中參加#include Linequ.h,以實現(xiàn)在該文件中可使用Linequ類。在GuassLineGUI

22、Dlg.cpp文件中參加以下全局變量的定義,以實現(xiàn)GuassLineGUIDlg類和Linequ類之間的通信,具體代碼如下:double a=/系數(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;double b4= 1.8471,1.7471,1.6471,1.5471;/方程右端項double *;/存放方程組的解編寫讀入數(shù)據(jù)按鈕的消息處理函數(shù),實現(xiàn)將矩陣和右端項的數(shù)據(jù)刷新到界面上,具體代碼如下:void CGu

23、assLineGUIDlg:OnBUTTONRead() / TODO: Add your control notification handler code herem_A00=a0; m_A01=a1; m_A02=a2; m_A03=a3;m_A10=a5; m_A11=a6; m_A12=a7; m_A13=a8;m_A20=a9; m_A21=a10; m_A22=a11; m_A23=a12;m_A30=a13; m_A31=a14; m_A32=a15; m_A33=a16;m_b0=b0; m_b1=b1; m_b2=b2; m_b3=b3;UpdateData(FALSE);編寫計算求解按鈕的消息處理函數(shù),實現(xiàn)將方程求解,具體代碼如下:void CGuassLineGUIDlg:OnButtonCalc() / TODO: Add your control notification handler code hereLinequ equ1(4);/定義一個四元方程組對象equ1.SetLinequ(a,b);/設(shè)置方程組*=new double4;if(equ1.Solve()/求解方程組equ1.Show*(*);/輸出方程組的解m_*0=*0;m_*1=*1;m_*2=*2;m_*3=*3;UpdateData(FALSE);elseMessag

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

評論

0/150

提交評論