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

1、合肥學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)系課程設(shè)計(jì)報(bào)告20092010 學(xué)年第2學(xué)期數(shù)據(jù)結(jié)構(gòu)與算法20 / 17課程設(shè)計(jì)名稱Dijkstra算法的實(shí)現(xiàn)學(xué)生學(xué)專業(yè)指導(dǎo)姓名張睿辰號(hào)0804012044班級(jí)08計(jì)科班教師王昆侖張貫虹2010年6月Dijkstra 算法的實(shí)現(xiàn)一、 問題分析與任務(wù)定義1 、課程設(shè)計(jì)題目 ：1.1 題目 ：對(duì)任意圖，選擇合適的數(shù)據(jù)結(jié)構(gòu)表示圖，在此基礎(chǔ)上實(shí)現(xiàn)求解最短路徑的 Dijkstra 算法1.2 要求 ：設(shè)計(jì)合理的數(shù)據(jù)結(jié)構(gòu)存儲(chǔ)圖，簡單有效的實(shí)現(xiàn)Dijkstra 算法。1.3 具體任務(wù) ：建立圖的存儲(chǔ)模塊，建立圖的輸出模塊，在建圖后從單源點(diǎn)開始求最短路徑，并顯示出來！2 、 原始數(shù)據(jù)的

2、輸入格式：2.1 建圖模塊： 2.1.1 數(shù)字2.2.2 數(shù)字 +空格+數(shù)字+空格 +數(shù)字 + 回車2.3 顯示模塊： 回車3、實(shí)現(xiàn)功能：3.1 建立有向圖3.2 顯示存儲(chǔ)的有向圖3.3 顯示從頂點(diǎn)到其他各頂點(diǎn)的最短路徑4、測試用例：4.1 正確數(shù)據(jù)：a）頂點(diǎn)：3;邊值信息：0 1 6; 0 2 4; 1 2 5; 2 0 6; 0 0 0;b）頂點(diǎn)：0;邊值信息：0 0 0;輸出結(jié)果 ： a） v0 到 v1 的最短路徑是6 ， v0 到 v2 的最短路徑是4b） 沒有最短路徑4.2 錯(cuò)誤數(shù)據(jù) ： a） 頂點(diǎn)： ab）頂點(diǎn)：2;邊值信息：0 3 6; 0 4 4; 13 5; 0 0 0;c

3、 ）頂點(diǎn)：3；邊值信息：0 1 a；輸出結(jié)果 ：邊值錯(cuò)誤，請(qǐng)從新輸入5、問題分析：實(shí)現(xiàn)本程序要解決以下幾個(gè)問題：5.1 如何存儲(chǔ)一個(gè)有向圖。5.2 如何在界面中輸出該有向圖。5.3 如何定義起始源點(diǎn)。5.4 如何選擇出最短路徑。5.5 找到的最短路徑如何輸出。二、 數(shù)據(jù)結(jié)構(gòu)的選擇和概要設(shè)計(jì)1 、 數(shù)據(jù)結(jié)構(gòu)的選擇：在圖的結(jié)構(gòu)中，任意兩個(gè)頂點(diǎn)之間都可能存在關(guān)系，比線性表和樹要復(fù)雜。由于不存在嚴(yán)格的前后順序， 因而不能采用簡單的數(shù)組來存儲(chǔ)圖 ;另一方面， 如果采用鏈表， 由 于圖中各頂點(diǎn)的度數(shù)不盡相同，最小度數(shù)和最大度數(shù)可能相差很大，如果按最大度數(shù)的頂點(diǎn)來設(shè)計(jì)鏈表的指針域，則會(huì)浪費(fèi)很多存儲(chǔ)單元，反之

4、，如果按照各個(gè)頂點(diǎn)設(shè)計(jì)不同 的鏈表結(jié)點(diǎn)，則會(huì)給操作帶來很大的困難。在此我選用鄰接矩陣的存儲(chǔ)結(jié)構(gòu)。采用鄰接矩陣存儲(chǔ)，很容易判斷圖中兩個(gè)頂點(diǎn)是 容相連，也容易求出各個(gè)頂點(diǎn)的度。不過任何事情都不是完美的，采用鄰接矩陣存儲(chǔ)圖 時(shí)，測試其邊的數(shù)目，必須檢查邊二維數(shù)組的所有元素，時(shí)間復(fù)雜度為O （吊），這對(duì)于頂點(diǎn)很多而邊較少的圖（稀疏圖）是非常不合算的。以鄰接矩陣存儲(chǔ)有向圖，如圖1中有向圖G所示，其鄰接矩陣為圖 2 cost 。05010OO45OOOO0155010OO20OO015OOOOOO20OO035OOOOOOOO300OOOOOOOO3OO0圖2.有向圖圖2.矩陣cost有向圖的鄰接矩陣in

5、tcostij 定義為 cost nn;2、概要設(shè)計(jì)2.1 對(duì)于最短路徑問題：最短路徑是在實(shí)際應(yīng)用中非常有用的工具，我們常見的兩種最短路徑是：（1）從某源點(diǎn)到其余各頂點(diǎn)之間的最短路徑。（2）每一段頂點(diǎn)之間的最短路徑在這里我們解決第一類問題。2.2 Dijkstra算法用于求最短路徑：Dijkstra算法是按路徑長度遞增的次序逐步產(chǎn)生源點(diǎn)到其他頂點(diǎn)間的最短路徑。算法建立一個(gè)頂點(diǎn)集合S,初始時(shí)該集合只有源點(diǎn) V0 ,然后逐步將已求得最短路徑的頂點(diǎn)加入到集合中，直到全部頂點(diǎn)都在集合S中，算法結(jié)束。2.3 Dijkstra算法思想設(shè)costi,j=0 , S為已經(jīng)求得最短路徑的頂點(diǎn)集合，distanc

6、ei數(shù)組的每個(gè)元素表示當(dāng)前狀態(tài)下源點(diǎn) V0到Vi的最短路徑。算法如下：1）初始化：S=V0, distancei=cost0,i。2）選擇一個(gè)終點(diǎn) Vj ,滿足 distancej=MIN distancei|Vi 6 V-S。3）把Vj加入到S中。4）修改distance數(shù)組元素，修改邏輯為對(duì)于所有不在S中的頂點(diǎn)Vi.if(distancej+costi,j distancei) distancei= distance0 +costi,j5)重復(fù)操作2)、3)、4),直到全部頂點(diǎn)加入到S中。2.4實(shí)現(xiàn)流程在任意圖中實(shí)現(xiàn)求最短路徑問題，第一步是要能成功的在內(nèi)存中輸入圖的信息，圖的信息有兩個(gè)，一

7、是頂點(diǎn)個(gè)數(shù)，二是每兩點(diǎn)之間的權(quán)值信息。當(dāng)建立圖之后，對(duì) 圖進(jìn)行遍歷才能使用 Dijkstra算法求出最短路徑；在完成了圖的建立之后，用Dijkstra 算法的思想，從單源點(diǎn)開始，求出到各個(gè)頂點(diǎn)的最短路徑，并能夠?qū)崿F(xiàn)顯示功能。 程序流程圖：Dijkstra算法流程圖:三、 詳細(xì)設(shè)計(jì)和編碼3.1 鄰接矩陣的定義：我們定義全局變量cost,dist 數(shù)組，方便在各子程序中的調(diào)用，加快了程序的運(yùn)行速度。int costMAXMAX;int distMAX;int n;cost 二維數(shù)組用于存放鄰接矩陣， 每個(gè)位置代表的值為圖中的權(quán)值， 其余用無窮大999 表示。dist 為輔助數(shù)組，圖中每個(gè)頂點(diǎn)對(duì)應(yīng)該

8、數(shù)組中的一個(gè)元素，這個(gè)元素存放當(dāng)前源點(diǎn)到該頂點(diǎn)的最短路徑。 此時(shí)的路徑指示當(dāng)前結(jié)果， 并不一定是最終的最短路徑。 隨著集合 S 的變化，其他頂點(diǎn)不斷地加入到集合中， 可能以這些新加入的頂點(diǎn)為 “橋梁” 產(chǎn)生比以前路徑更短的路徑， dist 數(shù)組元素的值是動(dòng)態(tài)變化的。n 是指圖中的頂點(diǎn)數(shù)目。3.2 結(jié)點(diǎn)結(jié)構(gòu)體的定義：structint num;int pnodeMAX;pathMAX;整型變量num是用來記錄求V0到每個(gè)頂點(diǎn)的最短路徑時(shí)所經(jīng)過的頂點(diǎn)的數(shù)目。數(shù)組 pnode 用來存放求V0 到每個(gè)頂點(diǎn)的最短路徑時(shí)所經(jīng)過的頂點(diǎn)，初始為V0。結(jié)構(gòu)體數(shù)組 path 為從 V0 到各頂點(diǎn)的最短路徑。3.3

9、 創(chuàng)建帶權(quán)有向圖初始化鄰接矩陣cost 中的值為無窮大，即任意兩個(gè)頂點(diǎn)之間不存在路徑。首先輸入該有向圖的頂點(diǎn)數(shù)n,然后依次輸入各個(gè)頂點(diǎn)及邊長(輸入的頂點(diǎn)的序號(hào)應(yīng)該小于頂點(diǎn)的數(shù)目)。輸入0 0 0結(jié)束。定義變量 contin,標(biāo)志輸入是否結(jié)束。若 contin=1 ,輸入繼續(xù)，若 contin=0 , 輸入完成。代碼：void creatgraph()/創(chuàng)建帶權(quán)有向圖int i,j,s,e,len,contin=1;printf(n 請(qǐng)輸入頂點(diǎn)個(gè)數(shù):);scanf(%d,&n);for(i=0;in;i+)for(j=0;j頂點(diǎn)，頂點(diǎn)，邊長:,i);scanf(%d%d%d,&s,&e,&len

10、);if(s=0 & e=0 & len=0)contin=0;else if(s=0 & s=0 & e0) / 輸入的頂點(diǎn)的序號(hào)應(yīng)該小于頂點(diǎn)的數(shù)目costse=len;i+;elseprintf(tt 邊值錯(cuò)誤，重復(fù)輸入 !n);display(n);/ 輸出所建數(shù)組getchar();3.4 鄰接矩陣的顯示在圖的鄰接矩陣顯示中，分別利用 for 循環(huán)輸出了矩陣的行列標(biāo)，使矩陣很明了。代碼：void display(int n1)int i,j;printf(n*所建圖的鄰接矩陣*n);*for(i=0;in1;i+)printf(%d,i); / 利用 for 循環(huán)輸出鄰接矩陣的行標(biāo)pr

11、intf(n);for(i=0;in1;i+)printf(%d,i);/利用for 循環(huán)輸出鄰接矩陣的列標(biāo)for(j=0;jn1;j+)printf(t%3d,costij,i,j); printf(n);3.5 Dijkstra 求最短路徑的實(shí)現(xiàn)設(shè)圖以鄰接矩陣cost 存儲(chǔ)，矩陣中各元素的值為各邊的權(quán)值。頂點(diǎn)間無邊時(shí)其對(duì)應(yīng)權(quán)值用無窮大表示。從頂點(diǎn) V0 到其它各頂點(diǎn)間的最短路徑的具體步驟如下：a) 變量定義：定義整型數(shù)組S口,這是一個(gè)頂點(diǎn)集合，初始時(shí)該集合只有源點(diǎn)V0,然后逐步將以求得最短路徑的頂點(diǎn)加入到該集合中，直到全部頂點(diǎn)都在集合 S 中，算法結(jié)束。定義兩個(gè)整型變量dis、 mindi

12、s 均用來標(biāo)志圖中最短的那一條路徑。b) 初始化：初始化 dist 數(shù)組的值即為 cost 數(shù)組中存放的權(quán)值。 disti=costv0i初始化求到每個(gè)頂點(diǎn)的最短路徑時(shí)都經(jīng)過初始化記錄經(jīng)過的頂點(diǎn)數(shù)都為 0 。初始化頂點(diǎn)集合s 為空，即還未開始。v0 頂點(diǎn)。 pathi.pnode0=v0 pathi.num=0;si=0;c) 源點(diǎn)的選擇:將 v0 頂點(diǎn)加入到頂點(diǎn)集合s 中。 sv0=1d) 利用 for 循環(huán)選擇一個(gè)終點(diǎn) Vj, 使其滿足 V0 到 Vj 距離最短， 同時(shí)將 Vj 加入集合 S 中。e) 根據(jù) j 頂點(diǎn)調(diào)整當(dāng)前的最短路徑， 若滿足 disti distj+costji, 則修

13、改 disti 的值。同時(shí) V0 到 Vi 的最短路徑中經(jīng)過的頂點(diǎn)數(shù)加1 ， 即 pathi.num+; 并將經(jīng)過的頂點(diǎn)存入數(shù)組 pnode 即 pathi.pnodepathi.num=jf) 此時(shí)一趟求最短路徑完畢，將終點(diǎn) V1 添加到路徑中。g)循環(huán)執(zhí)行d),e),f)操作，直到全部頂點(diǎn)加入到S中。代碼：void shortdjs()/ 求最短路徑int sMAX;int mindis,dis,i,j,v0=0,u=0; /mindis 標(biāo)志圖中最短的那一條路徑for(i=0;in;i+)/ 初始化disti=costv0i;pathi.pnode0=v0;pathi.num=0;si=

14、0;sv0=1;for(i=1;in;i+)/ 將最短路徑定點(diǎn)加入到 s 中mindis=up;for(j=1;jn;j+)/查找當(dāng)前的最短路徑if(sj=0 & distjmindis) u=j;mindis=distj;su=1;for(j=1;jdis) distj=dis;pathj.num+; pathj.pnodepathj.num=u; pathi.num+;pathi.pnodepathi.num=i; 3.6 最短路徑的輸出這段函數(shù)主要運(yùn)用 for 循環(huán)，依次輸出 V 0 到 Vi 的最短長度與最短路徑。void dispath()/輸出最短路徑int i,j;printf(

15、n 從 V0 到各頂點(diǎn)的最短路徑長度如下： n);printf( 起點(diǎn) -終點(diǎn) ) 最短長度 最短路徑 n);printf( n);for(i=1;iV%d): ,i);if(distiup)printf(t %d t,disti); elseprintf(tt); 顯示無窮大for(j=0;j,pathi.pnodej);printf(V%dn,pathi.pnodepathi.num); 四、 上機(jī)調(diào)試4 1 記錄調(diào)試過程中遇到的錯(cuò)誤和問題a) 當(dāng)輸入格式不符合程序要求時(shí)，會(huì)提示錯(cuò)誤輸入，但會(huì)出現(xiàn)死循環(huán)，可以定義一個(gè)標(biāo)志量 contin ，當(dāng)要停止的時(shí)候，命令contin=0 ，循環(huán)結(jié)束；

16、b) 當(dāng)兩頂點(diǎn)間沒有路徑時(shí)， 權(quán)值為無窮大， 但在本程序中只能用一個(gè)具體的數(shù)字999 代替抽象的無窮大。c) 在程序的調(diào)試過程可暫時(shí)多加一些輸出語句以便及時(shí)查看一下中間運(yùn)行情況， 并對(duì)程 序規(guī)格說明作調(diào)整和改動(dòng)。4.2 算法的時(shí)間和空間性能分析4.2.1 時(shí)間復(fù)雜度對(duì)于 n 個(gè)頂點(diǎn)的有向圖，求一個(gè)頂點(diǎn)到其他頂點(diǎn)的最短路徑的時(shí)間為 O（n） ，調(diào)整最短路徑的循環(huán)共執(zhí)行n-1 次，是二層循環(huán)，所以，時(shí)間復(fù)雜度是O （ n2） 。4.2.2 空間復(fù)雜度采用鄰接矩陣存儲(chǔ)有向圖， 應(yīng)處理每兩個(gè)頂點(diǎn)之間的關(guān)系， 所以空間復(fù)雜度為O（ n2 ） 。4.3 算法設(shè)計(jì)、調(diào)試的經(jīng)驗(yàn)和體會(huì)Dijkstra 算法在上

17、課的時(shí)候曾作為重點(diǎn)講過， 所以在做查找最短路徑的算法時(shí)很流暢， 但 是在輸出最短路徑的時(shí)候遇到了很大的阻力。 因?yàn)樵诙x結(jié)點(diǎn)時(shí)， 使用的是結(jié)構(gòu)體數(shù)組， 所 以當(dāng)處理 V0 到每個(gè)結(jié)點(diǎn)的最短路徑時(shí)，導(dǎo)致無法具體記錄經(jīng)過的頂點(diǎn)數(shù)，只能記錄源點(diǎn)、 終點(diǎn)前一頂點(diǎn)以及終點(diǎn)。所以本程序在輸出最短路徑時(shí)有較大的瑕疵，還需進(jìn)一步修改。5、 測試結(jié)果測試 1：驗(yàn)證當(dāng)兩點(diǎn)間不存在路徑時(shí)，程序是否正確。當(dāng)頂點(diǎn)間無路徑時(shí)，最短路徑為無窮大。程序正確。測試 2：輸入一組正確的數(shù)據(jù)，測試程序的正確性。通過測試，驗(yàn)證了程序是正確的。測試3：測試當(dāng)輸入錯(cuò)誤的時(shí)，程序是否正確。當(dāng)輸入錯(cuò)誤時(shí)，提示重新輸入，程序正確。6、 用戶使

18、用說明該程序可應(yīng)用在出行指南中， 用 020 表示出行地點(diǎn)， 輸入路徑， 得出最優(yōu)出行路線。用戶操作方法如下：1 、 輸入頂點(diǎn)個(gè)數(shù)：最大不超過20，請(qǐng)輸入羅馬數(shù)字，若輸入其他符號(hào)，會(huì)顯示警告；2 、 以“數(shù)字 數(shù)字 數(shù)字”的格式輸入圖的信息，輸入的數(shù)字0 即表示源點(diǎn)，前兩個(gè)數(shù)字應(yīng)小于頂點(diǎn)個(gè)數(shù)，最后一個(gè)數(shù)字應(yīng)小于999 。當(dāng)輸入“0 0 0 ”時(shí)，輸入完成；3 、 在輸入完成后，屏幕顯示鄰接矩陣與最短路徑。7、 參考文獻(xiàn)1 、 王昆侖 , 李紅編著 . 數(shù)據(jù)結(jié)構(gòu)與算法. 北京 : 中國鐵道出版社,2007.2 、 嚴(yán)蔚敏 , 陳文博編著. 數(shù)據(jù)結(jié)構(gòu)及算法教程. 北京 : 清華大學(xué)出版社,2001

19、八、 附錄#include #include #include#define MAX 20/最多頂點(diǎn)個(gè)數(shù)#define up 999/定義一個(gè)無窮大的值int costMAXMAX;/cost 為帶權(quán)鄰接矩陣int distMAX,n;/dist 為輔助數(shù)組，每個(gè)頂點(diǎn)對(duì)應(yīng)該數(shù)組中的一個(gè)元素，這個(gè)元素 存放當(dāng)前源點(diǎn)到該頂點(diǎn)的最短路徑。structint num;int pnodeMAX;初始為 v0pathMAX;void display(int n1)/ 記錄求 v0 到每個(gè)頂點(diǎn)的最短路徑時(shí)所經(jīng)過的頂點(diǎn)的數(shù)目/用來存放求v0 到每個(gè)頂點(diǎn)的最短路徑時(shí)所經(jīng)過的頂點(diǎn)，/path 為從 V0 到各頂點(diǎn)

20、的最短路徑int i,j;printf(n*所建圖的鄰接矩陣*n);*for(i=0;in1;i+)printf(%d,i); / 利用 for 循環(huán)輸出鄰接矩陣的行標(biāo)printf(n);for(i=0;in1;i+)printf(%d,i);/利用for 循環(huán)輸出鄰接矩陣的列標(biāo)for(j=0;jn1;j+)printf(t%3d,costij,i,j);printf(n);/輸出所建圖的鄰接矩陣void creatgraph()/創(chuàng)建帶權(quán)有向圖int i,j,s,e,len,contin=1; /contin 為標(biāo)志變量， 當(dāng) contin=1 時(shí)表示輸入正確， 當(dāng) contin=0 時(shí)，表

21、示輸入結(jié)束printf(n 請(qǐng)輸入頂點(diǎn)個(gè)數(shù):);scanf(%d,&n);for(i=0;in;i+)for(j=0;j 頂點(diǎn)，頂點(diǎn)，邊長:,i);scanf(%d%d%d,&s,&e,&len);if(s=0 & e=0 & len=0)contin=0;else if(s=0 & s=0 & e0) / 輸入的頂點(diǎn)的序號(hào)應(yīng)該小于頂點(diǎn)的數(shù)目costse=len;i+;elseprintf(tt 邊值錯(cuò)誤，重復(fù)輸入 !n);display(n);/ 輸出所建數(shù)組getchar();void shortdjs() / 求最短路徑int sMAX; 頂點(diǎn)集合，初始時(shí)該集合只有源點(diǎn)v0,然后逐步將以

22、求得最短路徑的頂點(diǎn)加入到該集合中，直到全部頂點(diǎn)都在集合 S 中，算法結(jié)束int mindis,dis,i,j,v0=0,u=0; /mindis 標(biāo)志圖中最短的那一條路徑for(i=0;in;i+)/ 初始化disti=costv0i; / 初始化 dist 數(shù)組，頂點(diǎn)v0 v1 v2 是與 0 1 2 一一對(duì)應(yīng)的pathi.pnode0=v0; / 初始化求到每個(gè)頂點(diǎn)的最短路徑時(shí)都經(jīng)過v0 頂點(diǎn)pathi.num=0;/初始化記錄經(jīng)過的頂點(diǎn)數(shù)都為0si=0;/頂點(diǎn)集合 s 為空，即還未開始sv0=1; /vo 定點(diǎn)加入到 s 中，等于 1 表示已進(jìn)入該集合for(i=1;in;i+)/ 將最短路徑定點(diǎn)加入到 s 中mindis=up;/ 記錄最短路徑for(j=1;jn;j+)/查找當(dāng)前的最短路徑if(sj=0 & distjmindis)u=j;