數(shù)據(jù)結(jié)構(gòu)課程設(shè)計報告 迪杰斯特拉算法的實現(xiàn)

1、數(shù)據(jù)結(jié)構(gòu)課程設(shè)計報告迪杰斯特拉算法的實現(xiàn)班級：軟件1408學(xué)號：1130505140825姓名：馬宏偉指導(dǎo)教師：石老師完成時間：2012年7月5日題目:Dijkstra算法的實現(xiàn)問題分析和任務(wù)定義1.1題 目：對任意圖，選擇合適的數(shù)據(jù)結(jié)構(gòu)表示圖，在此基礎(chǔ)上實現(xiàn)求解最短路 徑的Dijkstra算法。1.2要 求：對所設(shè)計的圖的數(shù)據(jù)結(jié)構(gòu)，提供必要的基本功能。1.3具體任務(wù)：建立圖的表示模塊，頂點的插入和刪除操作模塊；在建立圖之后從單 源點開始求最短路徑，并顯示出最短路徑長度及路徑途徑！2、實現(xiàn)功能：2.1建立有向圖2.2在建立好的有向圖中，顯示出來從源點到其他各個頂點的最短路徑長度及路徑途 徑。3

2、、測試用例：3.1正確數(shù)據(jù)：a）頂點：3；邊值信息：0 1 2； 1 0 3； 1 2 5； 2 1 6； 0 0 0；b）頂點：0；邊值信息：0 0 0；3.2錯誤數(shù)據(jù)：a）頂點：#；b）頂點：3；邊值信息：0 1 #；3.3參考用圖：圖1圖1.有向圖問題分析：題目要求選擇合適的數(shù)據(jù)結(jié)構(gòu)表示圖，本程序鄰接矩陣存儲結(jié)點和弧等圖的有關(guān)信息對用鄰接矩陣表示的有向圖，從某一頂點出發(fā)（稱為源點）到該圖其他各頂點（稱為終點）有無 路徑？最短路徑是什么？路徑長為多少？問題要求寫一個程序從有向網(wǎng)中的某一頂點出發(fā) 找出該頂點到其余各頂點的最短路徑。對鄰接矩陣arscnn中的每一個元素只能有三種 情況：當頂點i

3、到j(luò)無邊時，distancej= MAX;當頂點 i 到 j 有邊且權(quán)值為 edgesij時，distancej= edgesij;當頂點i到就經(jīng)過t有最短路徑時，distancej=distancet+edgestj;由于題目中沒有規(guī)定輸出格式，本程序以頂點序號的形式將最短路徑輸出到終端上去， 并輸出該最短路徑的長度及路徑途徑。二、數(shù)據(jù)結(jié)構(gòu)的選擇和概要設(shè)計1）數(shù)據(jù)存儲結(jié)構(gòu)以鄰接矩陣存儲有向圖，如圖2中有向圖G所示，其鄰接矩陣為圖3 edges。05010845880155010820801588820803588883008888380圖2.有向圖圖3,矩陣edges有向圖的鄰接矩陣arcs

4、ij定義為intedgesMAX_VERTEX_NUM MAX_VERTEX_NUM;2）概要設(shè)計對用鄰接矩陣表示的有向圖，從某一頂點出發(fā)（稱為源點）到該圖其他各頂點（稱為終點） 有無路徑？最短路徑是什么？路徑長為多少？問題要求寫一個程序從有向網(wǎng)中的某一頂點 出發(fā)找出該頂點到其余各頂點的最短路徑。對鄰接矩陣 edgesMAX_VERTEX_NUM MAX_VERTEX_NUM中的每一個元素只能有三種情況：當頂點i到 j 無 邊時，distance= MAX; 當頂點 i至Uj 有邊且 權(quán)值為edgesMAX_VERTEX_NUMMAX_VERTEX_NUM時，distancej=edgesMA

5、X_VERTEX_NUM MAX_VERTEX_NUM.當頂點 i到就經(jīng)過t有最短路徑時， distancej=distancet+edgestj;建立圖的表示模塊，頂點的插入和刪除操作模塊；在建立圖之后從單源點開始求最短 路徑，并顯示出來！流程圖如圖4圖4.程序流程圖(2)設(shè)計表示法(1)函數(shù)調(diào)用關(guān)系如圖下圖所示。create_MGraph()mainshortpath_DIJ()函數(shù)接口說明。void shortpath_DIJ(MGraph *mg,char i)VERTEX vexsMAX_VERTEX_NUM;int edgesMAX_VERTEX_NUMMAX_VERTEX_NUM

6、;char pathMAX_VERTEX_NUMMAX_VERTEX_NUM;int distanceMAX_VERTEX_NUM;/*求n個頂點，鄰接矩陣為edges，從源點i到各頂點的最短路徑，distance】記載 從源點到其余各頂點的最短路徑長度，path 為最短路徑途徑，數(shù)組vexs用來存儲頂 點，各部分的函數(shù)和各函數(shù)之間的關(guān)系采用鄰接矩陣表示法，構(gòu)造有向圖typedef struct VERTEX /定義頂點類型typedef struct MGraph/定義圖的類型MGraph *create_MGraph() /采用鄰接矩陣創(chuàng)建有向圖void shortpath_DIJ(MGr

7、aph *mg,char i)用 Dijkstra 算法求有向圖的 mg 的 i 頂點到其余 頂點的最短路徑void main()實現(xiàn)注釋系統(tǒng)限定鄰接矩陣的階n不超過max；為方便起見，系統(tǒng)假設(shè)有向網(wǎng)中邊的權(quán)為整型數(shù)；若有向網(wǎng)中頂點i到j(luò)之間無邊，則取值max。Dijkstra算法描述如下：輸入頂點個數(shù)n，鄰接矩陣edges和源點序號i。送初值：將 i 加入第一組 si=0；令 distancej=edgesij;(j=0,1,2,，n-1)重復(fù)n-1次做：在不屬于s的頂點U中，選取具有最小distancej值的頂點V；將V加入s；對不屬于s的頂點j做distancej=mindistance

8、j;diatancet+edgestj;/*distancej取(distancej,distancet+arcstj)兩個數(shù)中的最小值 */輸出各最短路徑的長度distancej及相應(yīng)的最短路徑pathj。3、詳細設(shè)計和編碼詳細設(shè)計：1)結(jié)點類型和指針類型typedef struct/定義頂點類型int num;/頂點序號char data;頂點信息VERTEX;typedef struct/定義圖的類型int n;/頂點數(shù)目int e;弧的數(shù)目VERTEX vexsMAX_VERTEX_NUM;/一維數(shù)組，存儲頂點int edgesMAX_VERTEX_NUMMAX_VERTEX_NUM;

9、二維數(shù)組，存儲邊或弧MGraph;采用數(shù)組(鄰接矩陣)表示法，構(gòu)造有向網(wǎng)mg的基本算法MGraph *create_MGraph()int i,j,k,w,n,e;char c;MGraph mg1,*mg=&mg1;printf(* 請輸入圖的頂點數(shù)：*ntt);/讀入頂點個數(shù)scanf(%d”,&n);printf(* 請輸入圖中弧的數(shù)目:*ntt);/讀入弧個數(shù)scanf(%d”,&e);mg-n=n;mg-e=e;getchar();printf(n*輸入頂點信息：*n);讀入第i個頂點信息for(i=0;ivexsi.data=c;mg-vexsi.num=i;/指定頂點的序號for

10、(i=0;in;i+)for(j=0;jedgesij=max;/先把所以的邊置空printf(-請輸入弧的信息，包括兩個頂點及弧的權(quán)值：n)； for(i=0;iedgesjk=w;return (mg);主要算法基本思想。單源最短路徑問題采用迪杰斯特拉(Dijkstra)提出的按路徑長度遞 增的次序產(chǎn)生最短路徑的算法。此算法把網(wǎng)中所有的頂點分成兩組，分別用s和U-s 表示。凡是以i為源點，已經(jīng)確定了最短路徑的終點屬于s，s的初態(tài)應(yīng)只包含i。另一 組U-s則是尚未確定最短路徑的頂點集合。U-s的初態(tài)應(yīng)是除源點外的網(wǎng)中所有頂點的 集合，按各頂點與i間的最短路徑長度遞增的次序，逐個把U-s中的頂

11、點加入到s中， 使得從i到s中各頂點的路徑長度始終不大于從i到U-s中各頂點的路徑長度。它的初 始狀態(tài)即是鄰接矩陣edges中第i行內(nèi)各列的值。顯然，從源點到各頂點的最短路徑中最短 的一條路徑應(yīng)為distancej=mindistancej （j=0,1，2，n-1）第一次求的最短路徑必然是（i，j），這時頂點號j應(yīng)從U-s中刪除而并入s。每當選出 一個頂點號j并使之并入s后，就要修改U-s中各頂點的最短路徑長度distance。對于 U-s中的某一個頂點j來說，其最短路徑長度或者仍是（i，j），或者是（i，t，j），決不可 能有其他選擇，也就是說，若distancet+edgestjedge

12、sij則修改distancej，使distancej= distancet+edgestj當U-s組中各頂點的distance：:進行修改后，再從中挑選出一個路徑長度路徑最小的頂 點，從U-s中刪除后再并入s。依次類推，就能求出所需的最短路徑長度。其中distance：、U、s都定義為整型數(shù)組，數(shù)組s用以標記那些已經(jīng)找到最短 路徑的頂點，若s：j為1表示已找到源點到頂點j的最短路徑；若s：j為0，則表示從源 點到頂點j的最短路徑尚未求得。用Dijkstra算法求有向圖的mg的i頂點到其余頂點j的最短路徑Dijkstra算法描述如下：（1）輸入頂點個數(shù)n，鄰接矩陣edges和源點序號i。（2）送

13、初值：將 i 加入第一組 s：i=0；令 distance：j=edges：i：j;（j=0,1,2,，n-1）（3）重復(fù)n-1次做：在不屬于s：的頂點U中，選取具有最小distance：j值的頂點V；將V加入s：；對不屬于s：的頂點j做distance：j=mindistance：j;diatance：t+edges：t：j;/*distance：j取（distance：j,distance：t+arcs：t：j）兩個數(shù)中的最小值 */（4）輸出各最短路徑的長度distance：j及相應(yīng)的最短路徑path：j。4、上機調(diào)試在調(diào)試過程中要特別注意函數(shù)調(diào)用時參數(shù)的傳遞問題，用數(shù)組名作為參數(shù)可進行

14、傳值調(diào)用， 因而可將函數(shù)中的運行結(jié)果傳遞給主調(diào)函數(shù)，得出正確結(jié)果；再一個要注意的是輸出結(jié)果時， 循環(huán)結(jié)束的條件應(yīng)為：i= #時退出循環(huán)。另外，上機前的靜態(tài)檢查不能忽視；程序的調(diào) 試過程可暫時多加一些輸出語句以便及時查看一下中間運行情況，并對程序規(guī)格說明作少量 調(diào)整和改動。算法的時間和空間性能分析1時間復(fù)雜度對于n個頂點的圖，求一個頂點到其他頂點的最短路徑，循環(huán)一次，加上修改最短 路徑的循環(huán)，是二層循環(huán)，所以，時間復(fù)雜度是O（n2）。2空間復(fù)雜度因為這個程序旨在求出最短路徑，但是必然要涉及到圖的存儲，而對于Dijkstra算法 弄清楚兩個頂點之間的關(guān)系又顯得尤為重要，所以，面對圖的幾種存儲結(jié)構(gòu)，

15、用鄰接表 是比較合適的，不過它的缺點是占用空間大，復(fù)雜度為O（n2+m*n）。5、測試結(jié)果及其分析執(zhí)行情況如下：輸入：5 3/*頂點個數(shù)為5，弧數(shù)為3*/0 1 2 3 4 /*頂點信息*/0 1 20 2 31 2 1 /*輸入有向網(wǎng)中帶權(quán)值的邊及權(quán)值*/0/*源點為0*/1/*源點為1*/#/*結(jié)束符*/結(jié)果如圖5所示。6、用戶使用說明程序執(zhí)行后，首先輸出：“輸入圖的頂點數(shù)：”輸入圖的頂點數(shù)后，輸出：“輸入輸入圖中弧的數(shù)目：”輸入輸入圖中弧的數(shù)目后，輸出：“輸入頂點信息：”輸入頂點信息后，輸出：“請輸入弧的信息，包括兩個頂點及弧的權(quán)值：”（用空格鍵隔） 輸入弧的信息，包括兩個頂點及弧的權(quán)值

16、后，輸出：“請輸入指定頂點i （輸入#號結(jié)束）：”輸入起始頂點名稱之后，輸出結(jié)果：o息SB10瑋1士口-二二二二二二二二二二二二二二二二二二二1入的的的的入的的的的入 輸1 2 3 4輸1 2 3 4輸 22 143 21-號tt1A 輸2 3 輸 1 輸 1為為信1徑為信1 點信路路點路徑路路點 頂路路短短頂短路短短頂 定短短曰籍曰取短曰籍 督取無無指無曰取無無指圖5.運行結(jié)果7、參考文獻序號：ISBN 978-7-113-07628-3/TP.2201作者：王昆侖李紅 書名：數(shù)據(jù)結(jié)構(gòu)與算法 出版地：北京市宣武區(qū)右安門西街8號 出版社名稱：中國鐵道出版社 出版社年份 20078、附錄/Dij

17、kstra算法實現(xiàn)#include iostream”#include fstream#include string#include using namespace std;#define MAX_VERTEX_NUM 100#define max 65536typedef structint num;char data;VERTEX;typedef structint n;int e;頂點的最大個數(shù)沒有連接弧的頂點的距離/定義頂點類型頂點序號頂點信息/定義圖的類型/頂點數(shù)目弧的數(shù)目VERTEX vexsMAX_VERTEX_NUM;/一維數(shù)組，存儲頂點int edgesMAX_VERTEX_

18、NUMMAX_VERTEX_NUM;二維數(shù)組，存儲邊或弧MGraph; MGraph *create MGraph()int i,j,k,w,n,e;char c;MGraph mg1,*mg=&mg1;printf(* 請輸入圖的頂點數(shù)：*ntt);/讀入頂點個數(shù)scanf(%d”,&n);printf(* 請輸入圖中弧的數(shù)目:*ntt);/讀入弧個數(shù)scanf(%d”,&e);mg-n=n;mg-e=e;getchar();printf(n*輸入頂點信息：*n);讀入第i個頂點信息for(i=0;ivexsi.data=c; mg-vexsi.num=i;/指定頂點的序號for(i=0;i

19、n;i+)for(j=0;jedgesij=max;/先把所以的邊置空printf(-請輸入弧的信息，包括兩個頂點及弧的權(quán)值：n)； for(i=0;iedgesjk=w; return (mg);void shortpath_DIJ(MGraph *mg,char i)/圖用鄰居矩陣存儲，i 是源點int inSMAX_VERTEX_NUM;/輔助數(shù)組用來標志頂點是否已經(jīng)在最短路徑的頂點集合中char pathMAX_VERTEX_NUMMAX_VERTEX_NUM;/存放路徑int distanceMAX_VERTEX_NUM;/到源點的距離int m,n,j,wm; int k=i-48; for(m=0;m(*mg).n;m+)/初始化各數(shù)組inSm=0; distancem = (*mg).edgeskm; if(distancem%d