1、課 程 設 計 任 務 書學院信息科學與工程專業通信工程學生姓名*學號*設計題目基于基于 DijkstraDijkstra 算法的最短路徑問題求解算法的最短路徑問題求解內容及要求：進行類的設計與實現，解決最短路徑問題。具體要求如下：（1） 采用圖的鄰接矩陣或鄰接表實現最短路徑問題中圖的存儲；（2） 采用 Dijkstra 算法求從某個源點到其余各頂點的最短路徑；（3） 將上述功能作為類的成員函數實現，編寫主函數測試上述功能。進度安排：第 17 周：分析題目，查閱課題相關資料，進行類設計、算法設計；第 18 周：程序的設計、調試與實現；第 19 周：程序測試與分析，撰寫課程設計報告，進行答辯驗收

2、。指導教師（簽字）：年 月 日學院院長（簽字）年 月 日目目 錄錄1 需求分析 .- 1 -2 算法基本原理 .- 1 -3 類設計 .- 2 -4 詳細設計 .- 3 -4.1 類的接口設計 .- 3 -4.2 類的實現 .- 5 -4.3 主函數設計 .- 10 -5 DOS 界面程序運行結果及分析 .- 11 -5.1 程序運行結果 .- 11 -5.2 運行結果分析.- 12 -6 基于 MFC 的圖形界面程序開發.- 13 -6.1 基于 MFC 的圖形界面程序設計.- 13 -6.2 程序測試.- 15-6.3 MFC 程序編寫總結.- 17 -7 參考文獻 .- 17- 1 -1

3、 需求分析需求分析Dijkstra 算法算法是由荷蘭計算機科學家艾茲格迪科斯徹發現的。算法解決的是有向圖中最短路徑問題。舉例來說，如果圖中的頂點表示城市，而邊上的權重表示著城市間開車行經的距離。 Dijkstra 算法可以用來找到兩個城市之間的最短路徑。Dijkstra 算法的輸入包含了一個有權重的有向圖 G，以及 G 中的一個來源頂點S。 我們以 V 表示 G 中所有頂點的集合。圖中的每一個邊，都是兩個頂點所形成的有序元素對。(u,v)表示從頂點 u 到 v 有路徑相連。 假設 E為所有邊的集合，而邊的權重則由權重函數 w: E 0, 定義。 因此，w(u,v)就是從頂點 u到頂點 v 的非

4、負花費值(cost)。 邊的花費可以想像成兩個頂點之間的距離。任兩點間路徑的花費值，就是該路徑上所有邊的花費值總和。 已知有 V 中有頂點 s 及 t，Dijkstra 算法可以找到 s 到 t 的最低花費路徑(i.e. 最短路徑)。 這個算法也可以在一個圖中，找到從一個頂點 s 到任何其他頂點的最短路徑。1如果將交通網絡化成帶權圖，假如用頂點表示城市，邊表示公路段，則由這些頂點和邊組成的圖可表示溝通個城市的公路圖，邊的權用以表示兩個城市之間的距離或者表示走過這段公路所需要的時間或通過這段路的難易程度等。作為司機和乘汽車的人，自然會關心如下兩個問題：（1）從甲地到乙地是否有公路？（2）從甲地到

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

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

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

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

9、從 Q 移動到 S。這個被選擇的頂點是 Q 中擁有最小的 du值的頂點。當一個頂點 u 從 Q 中轉移到了 S 中，算法對每條外接邊(u,v)進行拓展。 Dijkstra(G，D，s) /用 Dijkstra 算法求有向網 G 的源點 s 到各頂點的最短路徑長度 /以下是初始化操作 S=s；Ds=0； /設置初始的紅點集及最短距離 for( all i V-S )do /對藍點集中每個頂點 i Di=Gsi； /設置 i 初始的估計距離為 w /以下是擴充紅點集 for(i=0;iDk+Gkj) /新紅點 k 使原 Dj值變小時，用新路徑的長度修改 Dj， /使 j 離 s 更近。 Dj=Dk

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

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

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

13、kjdd- 5 -當一個搜索完,就是目前 到的最短距離。重復這一過程,最后當查完所有kijdij時,就為 到的最短距離。kijdij4 詳細設計詳細設計 首先，這個程序定義了一個類 class SPFA，通過此類定義鏈接矩陣，采用圖的鄰接矩陣或鄰接表實現最短路徑問題中圖的存儲，然后通過主函數 main調用 class 來實現，采用 Dijkstra 算法求從某個源點到其余各頂點的最短路徑。4.1 類的接口設計#includeusing namespace std;const int MAX=1000;const int INF=1000000000; class SPFApublic: int

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

15、訪問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(k=-1)/已經找不到有路可走的點return;usedk=true;for(j=0;jmin_+pathkj)/如果從 k 點走到 j 點的路很比原來的要短，那么更新disj=min_+pathkj;- 7 -;在類的成員函數實現過程中，設計了幾個循環語句，和判斷語句，定義點是否訪問過了,初始化為未訪問

16、，初始化一下到各個點的距離，已經找不到有路可走的點，if(!usedj&disjmin_+pathkj)/如果從 k 點走到 j 點的路很比原來的要短，那么更新4.3 主函數設計int main()/按照下面的數據格式輸入,-1 表示沒有路,自己到自己是 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;/源點暫時定為 0，你自己改吧a-Cal();for(i=0;in;i+)coutdisi=idisisrc=0;/源點暫時定為 0，然后通過循環語句，調用類中的函數，算出最短路徑。5 DOS 界面程序運行結果及分析界面程序運行結果及分析5.1 程序運行結果程序運行結果如圖 2 所示。- 9 -圖 2 程序運行結果5.2 運行結果分析整個程序中的矩陣存儲采用的是一維數組和動態內存分配方式。通過此類定義鏈接矩陣，采用圖的鄰接矩陣或鄰接表實現最短路徑問題中圖的存儲，然后通過主函數 main 調用 class 來實現，采用 Dijkstra 算法求從某個源點到其余各頂點的最短路徑。6

18、 基于 MFC 的圖形界面程序開發MFC 的圖形界面程序設計可在上述類設計的基礎上進行改造，MFC 的圖形界面程序與 DOS 界面程序的主要不同點是：MFC 圖形界面程序與 DOS 界面- 10 -程序的輸入輸出方式不同，DOS 界面程序采用字符交互式實現數據輸入輸出，主要通過 cin，cout 等 I/O 流實現，而 MFC 的圖形程序界面采用標準 Windows窗口和控件實現輸入輸出，因此必須在 MFC 類的框架下加入上面所設計的矩陣和方程組類，并通過圖形界面的輸入輸出改造來完成。6.1 基于 MFC 的圖形界面程序設計（1）界面設計）界面設計首先在 VC 中建立 MFC AppWizar

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

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

21、 工程。修改 class 文件具體包括：將顯示矩陣 PrintM()函數和顯示方程 PrintL()函數注釋掉，因為在圖形界面的程序上已經不需要連個函數承擔輸出功能了；將輸出方程組的解 ShowX()函數加入參數 double x變成 ShowX(double x)，以實現將所求的解輸出至參數 x 中，并最終完成在對話框界面上- 12 -的顯示；將全選主元高斯法求解函數 Solve() 中的兩處 cout 語句去掉，因為不需要也不能夠使用 cout 流實現輸出。在對話框類的實現文件 GuassLineGUIDlg.cpp 中加入#include Linequ.h，以實現在該文件中可使用 Lin

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

23、項的數據刷新到界面上，具體代碼如下：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);編寫計算求解按鈕的消息處理函數，實現將方程求解，具體代碼如下：void CGuassLineGUIDlg:OnButtonCalc() / TODO: Add your control notification handler code hereLinequ equ1(4); /定義一個四元方程組對象- 13 -equ1.SetLinequ(a,b); /設置方程組X=new double4;if(equ1.Solve() /求解方程組equ1.ShowX(X);/輸出方程組的解m_X0=X0;m_X1=X1;m_X2=X2;m_X3=X3;UpdateData(FALSE);elseMessageBox(求解失敗);/求解失敗退出按鈕比較簡單，代碼如下：void CGuassLineGUIDlg:OnBUTTONExit(