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

1、課 程 設(shè) 計(jì) 任 務(wù) 書(shū)學(xué)院信息科學(xué)與工程專業(yè)通信工程學(xué)生姓名*學(xué)號(hào)*設(shè)計(jì)題目基于基于 DijkstraDijkstra 算法的最短路徑問(wèn)題求解算法的最短路徑問(wèn)題求解內(nèi)容及要求：進(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)收

2、。指導(dǎo)教師（簽字）：年 月 日學(xué)院院長(zhǎng)（簽字）年 月 日目目 錄錄1 需求分析 .- 1 -2 算法基本原理 .- 1 -3 類(lèi)設(shè)計(jì) .- 2 -4 詳細(xì)設(shè)計(jì) .- 3 -4.1 類(lèi)的接口設(shè)計(jì) .- 3 -4.2 類(lèi)的實(shí)現(xiàn) .- 5 -4.3 主函數(shù)設(shè)計(jì) .- 10 -5 DOS 界面程序運(yùn)行結(jié)果及分析 .- 11 -5.1 程序運(yùn)行結(jié)果 .- 11 -5.2 運(yùn)行結(jié)果分析.- 12 -6 基于 MFC 的圖形界面程序開(kāi)發(fā).- 13 -6.1 基于 MFC 的圖形界面程序設(shè)計(jì).- 13 -6.2 程序測(cè)試.- 15-6.3 MFC 程序編寫(xiě)總結(jié).- 17 -7 參考文獻(xiàn) .- 17- 1 -1

3、 需求分析需求分析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, 定義。 因此，w(u,v)就是從頂點(diǎn) u到頂點(diǎn) v 的非

4、負(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）從甲地到

5、乙地有幾條公路，哪條公路最短或花費(fèi)的代價(jià)最??？這就是我們要討論的最短路徑問(wèn)題。2.迪杰斯特拉提出的一個(gè)求最短路徑的算法。其基本思想是：按路徑長(zhǎng)度遞增的順序，逐個(gè)產(chǎn)生各最短路徑。 3首先引進(jìn)輔助向量 dist，它的每一個(gè)分量 disti表示已經(jīng)找到的且從源點(diǎn)到每一個(gè)終點(diǎn)的當(dāng)前最短路徑長(zhǎng)度。它的初態(tài)為：如果從到有0viv0viv弧，則 disti為弧的權(quán)值；否則 disti為。其中，長(zhǎng)度為 distj=mindisti|V的路徑是從出發(fā)的長(zhǎng)度最短的一條最短路徑，此路徑為iv0v（，） 。0viv- 2 -2 算法基本原理算法基本原理根據(jù)以上分析，可以得到如下描述的算法：假設(shè)用帶權(quán)的鄰接矩陣 arc

6、eij來(lái)表示帶權(quán)有向圖，arceij表示弧上的權(quán)值。若不存在，則置 arceij為（在計(jì)算機(jī)上可ivjvivjv用允許的最大值代替） 。S 為已找到的從出發(fā)的最短路徑的終點(diǎn)的集合，它的0v初始狀態(tài)為空集。那么，從出發(fā)到圖上其余個(gè)頂點(diǎn)（終點(diǎn)）可能達(dá)到的最0viv短路徑長(zhǎng)度的初值為： disti=arceLocate Vex(G,)iS0viv選擇得jv distj=mindisti|V-Siv就是當(dāng)前求得的一條從出發(fā)的最短路徑的終點(diǎn)。令 S=Sj。jv0v修改從出發(fā)到集合 V-S 上任一頂點(diǎn)可達(dá)的最短頂點(diǎn)長(zhǎng)度。如果0vkv distj+arcejkdistk則修改 distk為 distk=di

7、stj+arcejk重復(fù)操作、共 n-1 次。由此求得從到圖上其余各頂點(diǎn)的最短路徑0v是依路徑長(zhǎng)度遞增的序列。用 Dijkstra 算法求有向圖 G 的頂點(diǎn)到其余頂點(diǎn) v 的最短路徑 Pv及其0v帶權(quán)長(zhǎng)度 Dv。 這個(gè)算法是通過(guò)為每個(gè)頂點(diǎn) v 保留目前為止所找到的從 s 到 v 的最短路徑來(lái)工作的。初始時(shí)，源點(diǎn) s 的路徑長(zhǎng)度值被賦為 0（ds=0）， 同時(shí)把所有其他頂點(diǎn)的路徑長(zhǎng)度設(shè)為無(wú)窮大，即表示我們不知道任何通向這些頂點(diǎn)的路徑（對(duì)于 V 中所有頂點(diǎn) v 除 s 外 dv= ）。當(dāng)算法結(jié)束時(shí)，dv中儲(chǔ)存的便是從 s 到v 的最短路徑，或者是無(wú)窮大（如果路徑不存在的話）。 - 3 - Dijs

8、tra 算法的基礎(chǔ)操作是邊的拓展：如果存在一條從 u 到 v 的邊，那么從 s到 v 的最短路徑可以通過(guò)將邊(u,v)添加到 s 到 u 的尾部來(lái)拓展。這條路徑的長(zhǎng)度是 du+w(u,v)。如果這個(gè)值比目前已知的 dv的值要小，我們可以用新值來(lái)替代當(dāng)前 dv中的值。拓展邊的操作一直執(zhí)行到所有的 dv都代表從 s 到 v 最短路徑的花費(fèi)。這個(gè)算法經(jīng)過(guò)適當(dāng)?shù)慕M織因而當(dāng) du達(dá)到它最終的值的時(shí)候，每條邊(u,v)都只被拓展一次。算法維護(hù)兩個(gè)頂點(diǎn)集 S 和 Q。集合 S 保留了我們已知的所有 dv的值已經(jīng)是最短路徑的值頂點(diǎn)，而集合 Q 則保留其他所有頂點(diǎn)。集合 S 初始狀態(tài)為空，而后每一步都有一個(gè)頂點(diǎn)

9、從 Q 移動(dòng)到 S。這個(gè)被選擇的頂點(diǎn)是 Q 中擁有最小的 du值的頂點(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；Ds=0； /設(shè)置初始的紅點(diǎn)集及最短距離 for( all i V-S )do /對(duì)藍(lán)點(diǎn)集中每個(gè)頂點(diǎn) i Di=Gsi； /設(shè)置 i 初始的估計(jì)距離為 w /以下是擴(kuò)充紅點(diǎn)集 for(i=0;iDk+Gkj) /新紅點(diǎn) k 使原 Dj值變小時(shí)，用新路徑的長(zhǎng)度修改 Dj， /使 j 離 s 更近。 Dj=Dk

10、+Gkj； - 4 -3 類(lèi)設(shè)計(jì)類(lèi)設(shè)計(jì) 從上面的算法分析可以看到，根據(jù)算法設(shè)計(jì)了類(lèi) class SPFA，public: int n;表示圖里面的點(diǎn)數(shù)，public: int pathMAXMAX;定義鏈接矩陣最多是1000 個(gè)點(diǎn)，public: int disMAX;定義源點(diǎn)到其他點(diǎn)的距離，public: int src;定義源點(diǎn)，bool usedMAX=false;定義點(diǎn)是否訪問(wèn)過(guò)了,初始化為未訪問(wèn)，初始化一下到各個(gè)點(diǎn)的距離，如果從 k 點(diǎn)走到 j 點(diǎn)的路很比原來(lái)的要短，那么更新，采用圖的鄰接矩陣或鄰接表實(shí)現(xiàn)最短路徑問(wèn)題中圖的存儲(chǔ)，采用Dijkstra 算法求從某個(gè)源點(diǎn)到其余各頂點(diǎn)的最短

11、路徑。第一步 先取意即到的距離為 0,而是對(duì)所賦的初 10W v1v1v jT v jT v值。第二步 利用已知,根據(jù)對(duì)進(jìn)行修正。 1W v min,jiijT vW vw jT v第三步 對(duì)所有修正后的求出其最小者。其對(duì)應(yīng)的點(diǎn)是所能 jT v kT vkv1v一步到達(dá)的點(diǎn)中最近的一個(gè),由于所有。因此任何從其它點(diǎn)中轉(zhuǎn)而jv 0W u jv到達(dá)的通路上的距離都大于直接到的距離,因此就是到kv1vkv kT v kT v1v的最短距離,所以在算法中令并從 s 中刪去,若 k=n 則kv kkW vT vkv就是到的最短路線,計(jì)算結(jié)束。否則令回到第二步,繼 knW vW v1vnvikvv續(xù)運(yùn)算,直

12、到 k=n 為止。這樣每一次迭代,得到到一點(diǎn)的最短距離,重復(fù)上述過(guò)程直到。1vkvknvvFloyd 算法的基本原理和實(shí)現(xiàn)方法為:如果一個(gè)矩陣其中表示 與ijDd0ijd i間的距離,若 與間無(wú)路可通,則為無(wú)窮大。 與間的最短距離存在經(jīng)過(guò)jijijdij與間的和不經(jīng)過(guò)兩種情況,所以可以令,n(n 為節(jié)點(diǎn)數(shù))。檢查ijkk1,2,3,kn與的值,在此,與分別為目前所知的 到與到的最短距離,因ijdikkjddikdkjdikkj此,就是 到經(jīng)過(guò)的最短距離。所以,若有,就表示從 出發(fā)ikkjddijkijikkjdddi經(jīng)再到的距離要比原來(lái)的 到距離短,自然把 到的重寫(xiě)成。每kjijijijdik

13、kjdd- 5 -當(dāng)一個(gè)搜索完,就是目前 到的最短距離。重復(fù)這一過(guò)程,最后當(dāng)查完所有kijdij時(shí),就為 到的最短距離。kijdij4 詳細(xì)設(shè)計(jì)詳細(xì)設(shè)計(jì) 首先，這個(gè)程序定義了一個(gè)類(lèi) class SPFA，通過(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)的最短路徑。4.1 類(lèi)的接口設(shè)計(jì)#includeusing namespace std;const int MAX=1000;const int INF=1000000000; class SPFApublic: int

14、 n;/表示圖里面的點(diǎn)數(shù)public: int pathMAXMAX;/定義鏈接矩陣最多是 1000 個(gè)點(diǎn)public: int disMAX;/定義源點(diǎn)到其他點(diǎn)的距離public: int src;/定義源點(diǎn)經(jīng)過(guò)公有派生，在類(lèi)的接口定義了圖里面的點(diǎn)數(shù)，定義鏈接矩陣最多是 1000 個(gè)點(diǎn)，定義源點(diǎn)到其他點(diǎn)的距離，定義源點(diǎn)經(jīng)過(guò)公有派生，這些變量 int n，int pathMAXMAX，int disMAX，int src 都是 public 型。4.2 類(lèi)的實(shí)現(xiàn)public:void Cal()- 6 -int i,j,k;bool usedMAX=false;/定義點(diǎn)是否訪問(wèn)過(guò)了,初始化為未

15、訪問(wèn)for(i=0;in;i+)/初始化一下到各個(gè)點(diǎn)的距離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(k=-1)/已經(jīng)找不到有路可走的點(diǎn)return;usedk=true;for(j=0;jmin_+pathkj)/如果從 k 點(diǎn)走到 j 點(diǎn)的路很比原來(lái)的要短，那么更新disj=min_+pathkj;- 7 -;在類(lèi)的成員函數(shù)實(shí)現(xiàn)過(guò)程中，設(shè)計(jì)了幾個(gè)循環(huán)語(yǔ)句，和判斷語(yǔ)句，定義點(diǎn)是否訪問(wèn)過(guò)了,初始化為未訪問(wèn)

16、，初始化一下到各個(gè)點(diǎn)的距離，已經(jīng)找不到有路可走的點(diǎn)，if(!usedj&disjmin_+pathkj)/如果從 k 點(diǎn)走到 j 點(diǎn)的路很比原來(lái)的要短，那么更新4.3 主函數(shù)設(shè)計(jì)int main()/按照下面的數(shù)據(jù)格式輸入,-1 表示沒(méi)有路,自己到自己是 0/*30 -1 -13 0 -13 4 030 100 13 0 -13 4 030 1 23 0 -13 4 0*/SPFA* a=new SPFA();couta-n;int i,j;- 8 -for(i=0;in;i+)for(j=0;jn;j+)cina-pathij;if(a-pathij=-1)a-pathij=INF;

17、a-src=0;/源點(diǎn)暫時(shí)定為 0，你自己改吧a-Cal();for(i=0;in;i+)coutdisi=idisisrc=0;/源點(diǎn)暫時(shí)定為 0，然后通過(guò)循環(huán)語(yǔ)句，調(diào)用類(lèi)中的函數(shù)，算出最短路徑。5 DOS 界面程序運(yùn)行結(jié)果及分析界面程序運(yùn)行結(jié)果及分析5.1 程序運(yùn)行結(jié)果程序運(yùn)行結(jié)果如圖 2 所示。- 9 -圖 2 程序運(yùn)行結(jié)果5.2 運(yùn)行結(jié)果分析整個(gè)程序中的矩陣存儲(chǔ)采用的是一維數(shù)組和動(dòng)態(tài)內(nèi)存分配方式。通過(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)的最短路徑。6

18、 基于 MFC 的圖形界面程序開(kāi)發(fā)MFC 的圖形界面程序設(shè)計(jì)可在上述類(lèi)設(shè)計(jì)的基礎(chǔ)上進(jìn)行改造，MFC 的圖形界面程序與 DOS 界面程序的主要不同點(diǎn)是：MFC 圖形界面程序與 DOS 界面- 10 -程序的輸入輸出方式不同，DOS 界面程序采用字符交互式實(shí)現(xiàn)數(shù)據(jù)輸入輸出，主要通過(guò) cin，cout 等 I/O 流實(shí)現(xiàn)，而 MFC 的圖形程序界面采用標(biāo)準(zhǔn) Windows窗口和控件實(shí)現(xiàn)輸入輸出，因此必須在 MFC 類(lèi)的框架下加入上面所設(shè)計(jì)的矩陣和方程組類(lèi)，并通過(guò)圖形界面的輸入輸出改造來(lái)完成。6.1 基于 MFC 的圖形界面程序設(shè)計(jì)（1）界面設(shè)計(jì)）界面設(shè)計(jì)首先在 VC 中建立 MFC AppWizar

19、d(exe)工程，名稱為 GuassLineGUI，并在向?qū)У?Step1 中選擇 Dialog based，即建立基于對(duì)話框的應(yīng)用程序，如下圖 45所示。圖 4 建立 MFC AppWizard(exe)工程圖 5 建立基于對(duì)話框的應(yīng)用程序- 11 -將對(duì)話框資源中的默認(rèn)對(duì)話框利用工具箱改造成如下界面，如圖 6 所示。（2）代碼設(shè)置）代碼設(shè)置為了能夠?qū)?duì)話框界面上的控件能夠與代碼聯(lián)系起來(lái)，需要為 24 個(gè) Edit Box 控件建立 Member Variables，按 Ctrl+w 鍵進(jìn)入 MFC ClassWizard 界面，選擇 Member Variables 選項(xiàng)卡，可顯示成員變量

20、設(shè)置界面，如圖 7 所示。圖 7 成員變量設(shè)置界面通過(guò)該界面設(shè)置與 24 個(gè) Edit Box 控件對(duì)應(yīng)的成員變量，具體如表 2 所示。表 2 控件基本信息控件 ID成員變量類(lèi)型成員變量名稱IDC_EDIT_A00 IDC_EDIT_A33doublem_1m_2IDC_EDIT_b0 IDC_EDIT_b3doublem_2m_3IDC_EDIT_X0 IDC_EDIT_X3doublem_3m_4下面是編寫(xiě)代碼的重要階段，可以借鑒在設(shè)計(jì)基于 DOS 界面的控制臺(tái)應(yīng)用程序的代碼，并將其作必要的改寫(xiě)，具體改寫(xiě)的步驟與內(nèi)容如下。將 class 文件，重新命名為 class.h，并將其加入 MFC

21、 工程。修改 class 文件具體包括：將顯示矩陣 PrintM()函數(shù)和顯示方程 PrintL()函數(shù)注釋掉，因?yàn)樵趫D形界面的程序上已經(jīng)不需要連個(gè)函數(shù)承擔(dān)輸出功能了；將輸出方程組的解 ShowX()函數(shù)加入?yún)?shù) double x變成 ShowX(double x)，以實(shí)現(xiàn)將所求的解輸出至參數(shù) x 中，并最終完成在對(duì)話框界面上- 12 -的顯示；將全選主元高斯法求解函數(shù) Solve() 中的兩處 cout 語(yǔ)句去掉，因?yàn)椴恍枰膊荒軌蚴褂?cout 流實(shí)現(xiàn)輸出。在對(duì)話框類(lèi)的實(shí)現(xiàn)文件 GuassLineGUIDlg.cpp 中加入#include Linequ.h，以實(shí)現(xiàn)在該文件中可使用 Lin

22、equ 類(lèi)。在 GuassLineGUIDlg.cpp 文件中加入以下全局變量的定義，以實(shí)現(xiàn)GuassLineGUIDlg 類(lèi)和 Linequ 類(lèi)之間的通信，具體代碼如下：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; /方程右端項(xiàng)double *X;/存放方程組的解編寫(xiě)讀入數(shù)據(jù)按鈕的消息處理函數(shù)，實(shí)現(xiàn)將矩陣和右端

23、項(xiàng)的數(shù)據(jù)刷新到界面上，具體代碼如下：void CGuassLineGUIDlg: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;

24、m_b3=b3;UpdateData(FALSE);編寫(xiě)計(jì)算求解按鈕的消息處理函數(shù)，實(shí)現(xiàn)將方程求解，具體代碼如下：void CGuassLineGUIDlg:OnButtonCalc() / TODO: Add your control notification handler code hereLinequ equ1(4); /定義一個(gè)四元方程組對(duì)象- 13 -equ1.SetLinequ(a,b); /設(shè)置方程組X=new double4;if(equ1.Solve() /求解方程組equ1.ShowX(X);/輸出方程組的解m_X0=X0;m_X1=X1;m_X2=X2;m_X3=X3;UpdateData(FALSE);elseMessageBox(求解失敗);/求解失敗退出按鈕比較簡(jiǎn)單，代碼如下：void CGuassLineGUIDlg:OnBUTTONExit(