基于Floyd算法的最短路徑問題的求解c++1

1、沈陽理工大學(xué)課程設(shè)計(jì)專用紙 摘要現(xiàn)實(shí)生活中許多實(shí)際問題的解決依賴于最短路徑的應(yīng)用，其中比較常用的是floyd算法。通過floyd算法使最短路徑問題變得簡(jiǎn)單化.采用圖的鄰接矩陣或鄰接表實(shí)現(xiàn)最短路徑問題中圖的存儲(chǔ)。采用Visual C+6。0的控制臺(tái)工程和MFC工程分別實(shí)現(xiàn)基于floyd算法求最短路徑的應(yīng)用。關(guān)鍵詞：最短路徑；floyd算法；鄰接矩陣;MFC工程目錄1需求分析12算法基本原理12。1 鄰接矩陣12。2 弗洛伊德算法23類設(shè)計(jì)23。1 類的概述23.2 類的接口設(shè)計(jì)33.3 類的實(shí)現(xiàn)44基于控制臺(tái)的應(yīng)用程序74.1 主函數(shù)設(shè)計(jì)74。2 運(yùn)行結(jié)果及分析85基于MFC的應(yīng)用程序95。1

2、圖形界面設(shè)計(jì)95。1 程序代碼設(shè)計(jì)115。3 運(yùn)行結(jié)果及分析20結(jié)論21參考文獻(xiàn)22II1 需求分析Floyd算法又稱為插點(diǎn)法，是一種用于尋找給定的加權(quán)圖中多源點(diǎn)之間最短路徑的算法.該算法名稱以創(chuàng)始人之一、1978年圖靈獎(jiǎng)獲得者、斯坦福大學(xué)計(jì)算機(jī)科學(xué)系教授羅伯特·弗洛伊德命名。假若要在計(jì)算機(jī)上建立一個(gè)交通咨詢系統(tǒng)則可以采用圖的結(jié)構(gòu)來表示實(shí)際的交通網(wǎng)絡(luò).這個(gè)資訊系統(tǒng)可以回答游客提出的各種問題。例如，一位旅客要從A城到B城,他希望選擇一條途中中轉(zhuǎn)次數(shù)最少的路線。假設(shè)圖中每一站都需要換車，則這個(gè)問題反映到圖上就是要找一條從頂點(diǎn)A到B所含邊的數(shù)目最少的路徑。我們只需從頂點(diǎn)A出發(fā)對(duì)圖作廣度優(yōu)先

3、搜索，一旦遇到頂點(diǎn)B就終止。由此所得廣度優(yōu)先生成樹上，從根頂點(diǎn)A到頂點(diǎn)B的路徑就是中轉(zhuǎn)次數(shù)最少的路徑，路徑上A與B之間的頂點(diǎn)就是途徑中的中轉(zhuǎn)站數(shù)。但是這只是一類最簡(jiǎn)單的圖的最短路徑的問題。有時(shí)對(duì)于旅客來說,可能更關(guān)心的是節(jié)省交通費(fèi)用；對(duì)于司機(jī)來說里程和速度則是他們感興趣的信息。為了在圖上標(biāo)示有關(guān)信息可對(duì)邊賦以權(quán)的值，權(quán)的值表示兩城市間的距離，或圖中所需時(shí)間，或交通費(fèi)用等等。此時(shí)路徑長度的量度就不再是路徑上邊的數(shù)目，而是路徑上邊的權(quán)值之和。邊賦以權(quán)值之后再結(jié)合最短路徑算法來解決這些實(shí)際問題。Floyd算法是最短路徑經(jīng)典算法中形式較為簡(jiǎn)單,便于理解的一種.2 算法基本原理2.1 鄰接矩陣鄰接矩陣(

4、Adjacency Matrix）：是表示頂點(diǎn)之間相鄰關(guān)系的矩陣。設(shè)G=（V,E）是一個(gè)圖,其中V=v1,v2，,vn。G的鄰接矩陣是一個(gè)具有下列性質(zhì)的n階方陣：(1)對(duì)無向圖而言，鄰接矩陣一定是對(duì)稱的，而且對(duì)角線一定為零（在此僅討論無向簡(jiǎn)單圖）,有向圖則不一定如此.(2）在無向圖中,任一頂點(diǎn)i的度為第i列所有元素的和,在有向圖中頂點(diǎn)i的出度為第i行所有元素的和,而入度為第i列所有元素的和。（3）用鄰接矩陣法表示圖共需要n2個(gè)空間,由于無向圖的鄰接矩陣一定具有對(duì)稱關(guān)系，所以扣除對(duì)角線為零外,僅需要存儲(chǔ)上三角形或下三角形的數(shù)據(jù)即可，因此僅需要nn-1/2個(gè)空間.2。2 弗洛伊德算法弗洛伊德算法使

5、用圖的鄰接矩陣arcsn+1n+1來存儲(chǔ)帶權(quán)有向圖。算法的基本思想是：設(shè)置一個(gè)n x n的矩陣A(k），其中除對(duì)角線的元素都等于0外，其它元素a(k）ij表示頂點(diǎn)i到頂點(diǎn)j的路徑長度，K表示運(yùn)算步驟.開始時(shí)，以任意兩個(gè)頂點(diǎn)之間的有向邊的權(quán)值作為路徑長度，沒有有向邊時(shí)，路徑長度為，當(dāng)K=0時(shí)， A (0）ij=arcsij，以后逐步嘗試在原路徑中加入其它頂點(diǎn)作為中間頂點(diǎn)，如果增加中間頂點(diǎn)后,得到的路徑比原來的路徑長度減少了，則以此新路徑代替原路徑,修改矩陣元素。具體做法為:第一步，讓所有邊上加入中間頂點(diǎn)1,取Aij與Ai1+A1j中較小的值作Aij的值，完成后得到A(1）；第二步，讓所有邊上加入

6、中間頂點(diǎn)2，取Aij與Ai2+A2j中較小的值，完成后得到A(2）,如此進(jìn)行下去，當(dāng)?shù)趎步完成后,得到A(n)，A(n）即為我們所求結(jié)果,A(n）ij表示頂點(diǎn)i到頂點(diǎn)j的最短距離.因此弗洛伊德算法可以描述為：A(0)ij=arcsij； /arcs為圖的鄰接矩陣A（k）ij=minA（k1） ij,A（k1） ik+A（k1） kj,其中 k=1，2,，n（1)定義一個(gè)n階方陣序列：D（1)，D(0），D(n1）。D(1） ij = G。arcsij；D（k) ij = min D（k1）ij,D(k-1）ik + D（k-1）kj ,k = 0,1，,n-1(2）其中D(0) ij是從頂點(diǎn)v

7、i 到vj中間頂點(diǎn)是v0的最短路徑的長度；D（k） ij是從頂點(diǎn)vi 到vj中間頂點(diǎn)的序號(hào)不大于k的最短路徑長度;D（n1）ij是從頂點(diǎn)vi 到vj的最短路徑長度。3 類設(shè)計(jì)3.1 類的概述類代表了某一批對(duì)象的共性和特征。類是對(duì)象的抽象。類這種數(shù)據(jù)類型中的數(shù)據(jù)既包含數(shù)據(jù)也包含操作數(shù)據(jù)的函數(shù).聲明類的一般形式：class 類名 private:私有的數(shù)據(jù)和成員函數(shù)；public：公用的數(shù)據(jù)和成員函數(shù)； ;定義對(duì)象:類名對(duì)象名；可以在類外定義成員函數(shù)，在函數(shù)名前加上類名，“:"是作用域限定符或稱作用域運(yùn)算符用它說明函數(shù)式屬于哪個(gè)類的。如下面程序中的voidMGraph：CreateMGr

8、aph(MGraph G）函數(shù)體3。2 類的接口設(shè)計(jì)includeiostream#include string#include stdio。h>using namespace std;define MaxVertexNum 100define INF 32767classMGraphprivate： char vertexMaxVertexNum； /頂點(diǎn)信息int edgesMaxVertexNumMaxVertexNum； /鄰接矩陣intn，e；/頂點(diǎn)數(shù)和邊數(shù)public： void CreateMGraph(MGraph &）; /構(gòu)造有向圖voidPpath(int1

9、00，int，int）； void Dispath（int100,int100,int）； /輸出最短路徑void Floyd（MGraph G); /Floyd算法的具體實(shí)現(xiàn)；首先將所需文件名寫好，定義類MGraph。在進(jìn)行類體構(gòu)造時(shí)將數(shù)據(jù)char vertexMaxVertexNum、int edgesMaxVertexNumMaxVertexNum和intn，e定義為私有數(shù)據(jù)，將成員函數(shù)void CreateMGraph(MGraph )、void Ppath（int100，int，int)、void Dispath（int100，int100,int）和void Floyd（MGrap

10、h G)定義為公用的，以便非類體內(nèi)的數(shù)據(jù)調(diào)用函數(shù).3。3 類的實(shí)現(xiàn)void MGraph：CreateMGraph(MGraph G）/構(gòu)造有向圖 inti，j，k,p； cout"請(qǐng)輸入頂點(diǎn)數(shù)和邊數(shù)："； cin>G。n>G.e； cout"請(qǐng)輸入頂點(diǎn)元素：" for （i=0；i<G。n；i+) cin>>G。vertexi； for (i=0;i<G.n；i+） for （j=0；j<G.n；j+） G。edgesij=INF; if （i=j) G。edgesij=0; for （k=0；k<G。e

11、；k+） cout"請(qǐng)輸入第”k+1”條弧頭弧尾序號(hào)和相應(yīng)的權(quán)值：”； cini>j>p； G.edgesij=p； void MGraph:：Ppath（int pathMaxVertexNum,inti,int j） /Ppath（)函數(shù)在path中遞歸輸出從頂點(diǎn)vi到vj的最短路徑. int k； k=pathij; if （k=1) / pathij=i時(shí)，頂點(diǎn)vi和vj之間無中間頂點(diǎn)，也就是說找到了始節(jié)點(diǎn) return； Ppath(path,i,k）； printf（”%d"，k）； Ppath(path,k，j）; void MGraph:Disp

12、ath(int AMaxVertexNum，int pathMaxVertexNum，int n）/輸出最短路徑的算法 inti，j； for (i=0；in；i+) for （j=0；j<n；j+) if （Aij=INF） if （i！=j) printf（"從%d到d沒有路徑n”，i,j）； else printf(” 從%d到%d=路徑長度：%d路徑：”，i，j，Aij）; printf（"%d，”，i)； Ppath（path，i，j)； printf(”dn”，j)； voidMGraph:：Floyd（MGraph G） int AMaxVertexNu

13、mMaxVertexNum,pathMaxVertexNumMaxVertexNum; inti,j，k; for （i=0；iG。n；i+） for （j=0；jG。n；j+） Aij=G。edgesij； pathij=1； for （k=0；kG。n;k+) /向vi與vj之間中n次加入中間頂點(diǎn) for （i=0；iG。n；i+） for （j=0;jG.n;j+） if （Aij>Aik+Akj） Aij=Aik+Akj； pathij=k；/ 表示從i節(jié)點(diǎn)到j(luò)節(jié)點(diǎn)，要經(jīng)過k節(jié)點(diǎn) Dispath（A，path,G.n）； 4 基于控制臺(tái)的應(yīng)用程序4。1主函數(shù)設(shè)計(jì)int main（

14、)MGraph G；G。CreateMGraph(G);G。Floyd(G）；return 0;在程序的主函數(shù)部分,定義一個(gè)MGrapha類的對(duì)象G，調(diào)用成員函數(shù)CreateMGraph（）和Floyd()分別完成了采用圖的鄰接矩陣實(shí)現(xiàn)最短路徑問題中圖的存儲(chǔ)和采用Floyd算法求每一對(duì)頂點(diǎn)的最短路徑的任務(wù)。4.2 運(yùn)行結(jié)果及分析將待測(cè)圖的相關(guān)數(shù)據(jù)輸入則得到如圖1的運(yùn)行結(jié)果.圖1 程序運(yùn)行結(jié)果從圖1可以看出：整個(gè)程序中的矩陣存儲(chǔ)采用的是一維數(shù)組和動(dòng)態(tài)內(nèi)存分配方式。通過此類定義鄰接矩陣，采用圖的鄰接矩陣實(shí)現(xiàn)最短路徑問題中圖的存儲(chǔ)，然后通過主函數(shù)main調(diào)用class來實(shí)現(xiàn),采用Floyd算法求每對(duì)

15、頂點(diǎn)間最短路徑從某個(gè)源點(diǎn)到其余各頂點(diǎn)的最短路徑。將圖的基本信息輸入,頂點(diǎn)數(shù)和邊數(shù)4、8，頂點(diǎn)元素A、B、C、D,8條弧各自的序號(hào)和權(quán)值.運(yùn)行程序得出每對(duì)頂點(diǎn)間的最短路徑長度和路徑?；贔loyd算法成功的解決了最短路徑問題.5 基于MFC的應(yīng)用程序MFC的圖形界面程序與DOS界面程序的主要不同點(diǎn)是：MFC圖形界面程序與DOS界面程序的輸入輸出方式不同,DOS界面程序采用字符交互式實(shí)現(xiàn)數(shù)據(jù)輸入輸出,主要通過cin，cout等I/O流實(shí)現(xiàn),而MFC的圖形程序界面采用標(biāo)準(zhǔn)Windows窗口和控件實(shí)現(xiàn)輸入輸出，因此必須在MFC類的框架下加入上面所設(shè)計(jì)的矩陣和方程組類，并通過圖形界面的輸入輸出改造來完成

16、。5。1圖形界面設(shè)計(jì)首先在VC中建立MFC AppWizard（exe）工程，名稱為最短路徑1203060213,并在向?qū)У腟tep1中選擇Dialog based，即建立基于對(duì)話框的應(yīng)用程序，如下圖23所示。圖2建立MFC AppWizard（exe）工程圖3 建立基于對(duì)話框的應(yīng)用程序?qū)?duì)話框資源中的默認(rèn)對(duì)話框利用工具箱改造成如下界面，如圖4所示。圖4表達(dá)式求值程序界面設(shè)計(jì)在圖4的設(shè)計(jì)過程中，選擇文件按鈕用于進(jìn)行文件的選擇，選擇文件后頂點(diǎn)個(gè)數(shù)也隨之顯示；起點(diǎn)和終點(diǎn)編輯框分別用于輸入起點(diǎn)終點(diǎn)信息；提交按鈕用于輸出最終結(jié)果。5。1 程序代碼設(shè)計(jì)為了能夠?qū)?duì)話框界面上的控件能夠與代碼聯(lián)系起來，需要

17、為5個(gè)Edit Box控件建立Member Variables，按Ctrl+w鍵進(jìn)入MFC ClassWizard界面,選擇Member Variables選項(xiàng)卡，可顯示成員變量設(shè)置界面，如圖5所示。圖5成員變量設(shè)置界面通過該界面設(shè)置與5個(gè)Edit Box控件對(duì)應(yīng)的成員變量,具體如表1所示.表1 控件基本信息控件ID成員變量類型成員變量名稱IDC_EDIT_ENDintm_intEndIDC_EDIT_STARTintm_intStartIDC_EDIT_RESULTCstringm_intResulIDC_EDIT_INFOCstringm_strFileinfoIDC_EDIT_NUMIn

18、tm_nNum在MFC中的主要代碼：(1）.Ex_FloydDlg。cpp中的代碼為：void CEx_exFloydDlg:：OnButtonSel（） /選擇文件,并將文件中的數(shù)據(jù)保存到數(shù)組中/ TODO: Add your control notification handler code hereCFileDialog file（TRUE， NULL， NULL， NULL， _T(”（*。txt）。txt(.doc）.doc所有文件 （。*）*。 |"），NULL）； /*獲得文件名*/CStringstrFileName；if(file.DoModal（） = IDOK)

19、m_strFileInfo = file.GetFileName（）；if（m_strFileInfo.IsEmpty（）MessageBox（"你還沒有選擇任何文件！”)；return；elseMessageBox（”你選擇文件：”+ m_strFileInfo+”請(qǐng)輸入起點(diǎn)和終點(diǎn)”）;GetDlgItem(IDC_EDIT_START）->EnableWindow（true);GetDlgItem（IDC_EDIT_END）EnableWindow（true）;GetDlgItem（IDC_BUTTON_SUBMIT）EnableWindow(true)；/將文件的數(shù)據(jù)讀入

20、到數(shù)組中CStdioFilefp；if（！fp.Open（m_strFileInfo，CFile：modeRead)）MessageBox（"文件打開失??！”）;return；int i=0;CStringstr；char temp；BOOL bread = fp。ReadString（str）；temp = str.GetBuffer（0）；n=atoi（temp）；counts=n*n;int tp; tp=new intcounts+1；m_nNUM=n；c=new intn+1；for（i=1； i<=n； i+）ci= new int n+1；a=new int*n+

21、1；for(i=1； i<=n； i+）ai= new int n+1；r=new intn+1;for(i=1； i=n； i+）ri= new int n+1;bread = fp。ReadString（str）;i=0;while(bread)temp = str。GetBuffer（0);tpi+ = atoi（temp）；bread = fp。ReadString（str）；fp。Close()；/將一維數(shù)組轉(zhuǎn)化為二維數(shù)組放到數(shù)組c中for(i = 0； i<counts； i+)if(tpi ！= 1)ci/n+1in+1 = tpi；elseci/n+1in+1 =

22、maxint；UpdateData（FALSE)；voidCEx_exFloydDlg：Ex_floyd（intn,int c，int a,int r)inti,j，k；for(i=1； i<=n； i+）for（j=1; j=n； j+）aij=cij;rij=0;for（i=1； i=n; i+)for（j=1; j<=n; j+)for（k=1; k=n； k+）if（aik+akjaij)aij=aik+akj；rij=k；intCEx_exFloydDlg:：Ex_output(int *r，inti,int j）int k；if（rij!=0)k=rij；Ex_outp

23、ut(r,i,k);strRes。Format("%d>”，k）；m_strResult += strRes;Ex_output（r,k，j); return 0;void CEx_exFloydDlg：:OnButtonSubmit（） /執(zhí)行floyd算法計(jì)算最優(yōu)值和最優(yōu)解/ TODO： Add your control notification handler code hereUpdateData（TRUE）; /接受編輯框的數(shù)據(jù)CStringstrData； Ex_floyd(n，c，a，r）； if（m_intStart>nm_intStart1）Messag

24、eBox(”您輸入的起點(diǎn)有誤，請(qǐng)重新輸入"）；if（m_intEnd>n|m_intEnd1)MessageBox(”您輸入的終點(diǎn)有誤，請(qǐng)重新輸入”）；strData。Format（"起點(diǎn)為:d”，m_intStart);m_strResult += strData + ”rn” ；strData。Format（”終點(diǎn)為:%d”，m_intEnd）；m_strResult += strData + ”rn"strData。Format（”最優(yōu)值："）shortestdd=dn”，m_intStart，m_intEnd，am_intStartm_in

25、tEnd）；m_strResult += strData + ”rn"；strRes。Format（”最佳路徑：d”，m_intStart）；m_strResult += strRes；Ex_output（r，m_intStart，m_intEnd);strRes.Format（”%d”，m_intEnd)；m_strResult += strRes；UpdateData（FALSE)； /更新編輯框的數(shù)據(jù)(2）Ex_FloydDlg。h中的主要代碼為：classCEx_exFloydDlg : public CDialog/ Constructionpublic:CEx_exFlo

26、ydDlg（CWnd pParent = NULL）；/ standard constructorvoidEx_floyd (intn，int c，int *a，int *r）；intEx_output（int *r,inti，int j); / Dialog Data/AFX_DATA(CEx_exFloydDlg)enum IDD = IDD_EX_EXFLOYD_DIALOG ;CStringm_strFileInfo；intm_intEnd；intm_intStart；CStringm_strResult；intm_nNUM；protected：HICON m_hIcon;int n

27、； /圖形中頂點(diǎn)的個(gè)數(shù)int a； /最優(yōu)值矩陣int c;/頂點(diǎn)之間的距離矩陣int r；/路由矩陣int counts;int tp；CStringstrRes； / Generated message map functions/AFX_MSG(CEx_exFloydDlg）virtual BOOL OnInitDialog（）；afx_msg void OnSysCommand（UINT nID， LPARAM lParam)；afx_msg void OnPaint（);afx_msg HCURSOR OnQueryDragIcon（）；afx_msg void OnButtonSe

28、l（)；afx_msg void OnButtonSubmit（）;(3）兩個(gè)外部調(diào)用函數(shù)模塊:voidCEx_exFloydDlg：Ex_floyd（intn，int *c,int *a,int r）inti，j，k;for（i=1; i=n； i+)for(j=1; j=n; j+)aij=cij；rij=0;for(i=1； i=n； i+)for（j=1； j=n； j+）for（k=1； k<=n; k+）if（aik+akjaij）aij=aik+akj；rij=k；intCEx_exFloydDlg:：Ex_output(int *r，inti，int j）int k;if

29、(rij!=0）k=rij;Ex_output（r，i，k)；strRes。Format（"%d”，k)；m_strResult += strRes；Ex_output(r，k，j）； return 0；if(file。DoModal（) = IDOK）m_strFileInfo = file。GetFileName（);if（m_strFileInfo.IsEmpty(）)MessageBox(”你還沒有選擇任何文件！”）;return;elseMessageBox(”你選擇文件：”+ m_strFileInfo+”請(qǐng)輸入起點(diǎn)和終點(diǎn)”);GetDlgItem（IDC_EDIT_ST

30、ART)-EnableWindow（true）；GetDlgItem（IDC_EDIT_END)>EnableWindow（true)；GetDlgItem（IDC_BUTTON_SUBMIT）>EnableWindow（true)；/將文件的數(shù)據(jù)讀入到數(shù)組中CStdioFilefp；if(！fp。Open（m_strFileInfo,CFile：modeRead)MessageBox（”文件打開失敗！”)；return；int i=0；CStringstr;char* temp;BOOL bread = fp.ReadString（str）；temp = str。GetBuffe

31、r（0）；n=atoi(temp）；counts=nn;int *tp； tp=new intcounts+1;m_nNUM=n；c=new int*n+1；for(i=1； i=n； i+）ci= new int n+1;a=new int*n+1;for（i=1； i=n； i+）ai= new int n+1；r=new intn+1;for（i=1； i=n； i+）ri= new int n+1;bread = fp.ReadString(str);i=0；while(bread）temp = str。GetBuffer（0）；tpi+ = atoi（temp);bread = fp

32、.ReadString(str)；fp.Close（）；/將一維數(shù)組轉(zhuǎn)化為二維數(shù)組放到數(shù)組c中for（i = 0; i<counts； i+）if(tpi != 1)ci/n+1in+1 = tpi;elseci/n+1in+1 = maxint；UpdateData（FALSE）;5.3 運(yùn)行結(jié)果及分析先選擇“選擇文件按鈕"，在其中選擇一個(gè)文件后如1。txt。會(huì)在頂點(diǎn)個(gè)數(shù)只讀編輯框中顯示出你所選文件中的頂點(diǎn)個(gè)數(shù),分別在起點(diǎn)和終點(diǎn)編輯框中輸入起點(diǎn)和終點(diǎn)，在點(diǎn)擊提交，會(huì)出現(xiàn)如圖5運(yùn)行界面。圖5單擊提交按鈕后的界面在圖5中可以看出：進(jìn)行操作時(shí)，單擊選擇文件框，選擇所需要的文檔,該文檔存儲(chǔ)了待測(cè)圖的全部信息，隨即生成頂點(diǎn)個(gè)數(shù).將你所要測(cè)的最短路徑的一對(duì)頂點(diǎn)的起點(diǎn)和終點(diǎn)輸入相應(yīng)位置.待測(cè)信息輸入