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

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

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

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

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

5、X_VERTEX_NUM MAX_VERTEX_NUM.當(dāng)頂點(diǎn) i到就經(jīng)過t有最短路徑時(shí)， distancej=distancet+edgestj;建立圖的表示模塊，頂點(diǎn)的插入和刪除操作模塊；在建立圖之后從單源點(diǎn)開始求最短 路徑，并顯示出來！流程圖如圖4圖4.程序流程圖(2)設(shè)計(jì)表示法(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個(gè)頂點(diǎn)，鄰接矩陣為edges，從源點(diǎn)i到各頂點(diǎn)的最短路徑，distance】記載 從源點(diǎn)到其余各頂點(diǎn)的最短路徑長(zhǎng)度，path 為最短路徑途徑，數(shù)組vexs用來存儲(chǔ)頂 點(diǎn)，各部分的函數(shù)和各函數(shù)之間的關(guān)系采用鄰接矩陣表示法，構(gòu)造有向圖typedef struct VERTEX /定義頂點(diǎn)類型typedef struct MGraph/定義圖的類型MGraph *create_MGraph() /采用鄰接矩陣創(chuàng)建有向圖void shortpath_DIJ(MGr

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

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

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

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

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

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

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

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

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

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

17、kstra算法實(shí)現(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;頂點(diǎn)的最大個(gè)數(shù)沒有連接弧的頂點(diǎn)的距離/定義頂點(diǎn)類型頂點(diǎn)序號(hào)頂點(diǎn)信息/定義圖的類型/頂點(diǎn)數(shù)目弧的數(shù)目VERTEX vexsMAX_VERTEX_NUM;/一維數(shù)組，存儲(chǔ)頂點(diǎn)int edgesMAX_VERTEX_

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

19、n;i+)for(j=0;jedgesij=max;/先把所以的邊置空printf(-請(qǐng)輸入弧的信息，包括兩個(gè)頂點(diǎn)及弧的權(quán)值：n)； for(i=0;iedgesjk=w; return (mg);void shortpath_DIJ(MGraph *mg,char i)/圖用鄰居矩陣存儲(chǔ)，i 是源點(diǎn)int inSMAX_VERTEX_NUM;/輔助數(shù)組用來標(biāo)志頂點(diǎn)是否已經(jīng)在最短路徑的頂點(diǎn)集合中char pathMAX_VERTEX_NUMMAX_VERTEX_NUM;/存放路徑int distanceMAX_VERTEX_NUM;/到源點(diǎn)的距離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