軟件基礎(chǔ)課程設(shè)計(jì)--從某個(gè)源點(diǎn)到其余各頂點(diǎn)的最短路徑

1、<p>　　軟件設(shè)計(jì)基礎(chǔ)課程設(shè)計(jì)</p><p>　　題 目： 從某個(gè)源點(diǎn)到其余各頂點(diǎn)的最短路徑 </p><p>　　學(xué) 院： 信息與通信工程學(xué)院 </p><p>　　專 業(yè)： 通信工程專業(yè)

2、 </p><p>　　學(xué)生姓名： </p><p>　　班級(jí)/學(xué)號(hào)： </p><p>　　指導(dǎo)老師：

3、 </p><p>　　起止時(shí)間： 2013-9-22 至 2013-11-6 </p><p><b>　　摘要 </b></p><p>　　本次課程設(shè)計(jì)的問題：假設(shè)西安、北京、沈陽、武漢4個(gè)城市構(gòu)成小型交通網(wǎng)，4個(gè)城市表示圖的4個(gè)頂點(diǎn)，它們構(gòu)成了無

4、向連通圖。以北京為源點(diǎn)，求北京到西安的最短路徑；求北京到沈陽的最短路徑；北京到武漢的最短路徑。</p><p>　　本次課程設(shè)計(jì)中應(yīng)用Dijkstra算法求最短路徑。通過一個(gè)圖的權(quán)值矩陣求出它的每兩點(diǎn)間的最短路徑矩陣，從圖的帶權(quán)鄰接矩陣arcs(n×n)開始，遞歸地進(jìn)行n次更新，按一個(gè)公式，構(gòu)造出矩陣S(1)，又用同樣的公式由S(1)構(gòu)造出S(2)…最后又用同樣的公式由S(n-1)構(gòu)造出矩陣S(n)。矩

5、陣S(n)的i行j列元素便是i號(hào)頂點(diǎn)到j(luò)號(hào)頂點(diǎn)的最短路徑長度，稱S(n)為圖的距離矩陣，同時(shí)還可引入一個(gè)后繼節(jié)點(diǎn)矩陣p[j][k]來記錄兩點(diǎn)間的最短路徑。</p><p>　　本次試驗(yàn)進(jìn)行的是無向的計(jì)算，不同城市之間的距離由開始進(jìn)行輸入，最后顯示兩個(gè)城市之間的最短路徑。</p><p><b>　　目錄</b></p><p><b>

6、;　　任務(wù)書1</b></p><p><b>　　摘要2</b></p><p><b>　　目錄3</b></p><p><b>　　正文4</b></p><p>　　一、應(yīng)用迪科斯徹（Dijkstra）算法計(jì)算最短路徑4</p>&

7、lt;p>　　二、Dijkstra 求最短路徑的基本思想4</p><p>　　三、Dijkstra 求最短路徑的步驟4</p><p><b>　　四、程序說明5</b></p><p><b>　　五、功能實(shí)現(xiàn)5</b></p><p>　　六、程序設(shè)計(jì)（二）12</p&g

8、t;<p>　　七、課程設(shè)計(jì)總結(jié)16</p><p><b>　　參考文獻(xiàn)17</b></p><p><b>　　源代碼18</b></p><p>　　應(yīng)用迪科斯徹（Dijkstra）算法計(jì)算最短路徑</p><p>　　假設(shè)西安、北京、沈陽、武漢4個(gè)城市構(gòu)成小型交通網(wǎng)，4個(gè)

9、城市表示圖的4個(gè)頂點(diǎn)，他們構(gòu)成了無向連通圖。以北京為源點(diǎn)，求北京到西安的最短路徑；求北京到沈陽的最短路徑；求北京到武漢的最短路徑。</p><p>　　這里路徑指兩頂點(diǎn)間的通路，路徑的長度指所有經(jīng)過的邊的總長?！白疃搪窂健钡膯栴}指當(dāng)兩個(gè)頂點(diǎn)間通路多于一條時(shí)，如何找出邊長總和為最短的那條。Dijkstra提出按路徑長度遞增的次序求最短路徑的方法。</p><p>　　Dijkstra 求最短

10、路徑的基本思想</p><p>　　把頂點(diǎn)分成兩組，第一組是已確定最短路徑的結(jié)點(diǎn)的集合，第二組是尚未確定最短路徑的結(jié)點(diǎn)的集合。按路徑長度遞增的次序逐個(gè)把第二組的頂點(diǎn)放到第一組中。設(shè)求從v0到其它各頂點(diǎn)間的最短路徑,則在任意時(shí)刻，從v0到第一組各頂點(diǎn)間的最短路徑都不大于從v0到第二組各頂點(diǎn)間的最短路徑。 </p><p>　　Dijkstra 求最短路徑的步驟 </p><

11、;p>　　設(shè)圖以鄰接矩陣arcs存儲(chǔ)，矩陣中各元素的值為各邊的權(quán)值。頂點(diǎn)到自身的權(quán)值用0表示，頂點(diǎn)間無邊時(shí)其對應(yīng)權(quán)值用-1表示。從頂點(diǎn)v0到其它各頂點(diǎn)間的最短路徑的具體步驟如下： </p><p>　　（1）初始化：第一組（集合s）只含頂點(diǎn)v0,第二組（集合v-s）含有圖中其余頂點(diǎn)。設(shè)一D向量，其下標(biāo)是各頂點(diǎn)，元素值是頂點(diǎn)v0到各頂點(diǎn)的邊的權(quán)值。若v0到某頂點(diǎn)無邊，D向量中的對應(yīng)值為-1。 </p&g

12、t;<p>　?。?）選D中最小的權(quán)值，將其頂點(diǎn)（j）加入s集合。 </p><p><b>　　s=s {j} </b></p><p>　?。?）修改從頂點(diǎn)v0到集合t(t=V-s)中各頂點(diǎn)的最短路徑長度,如果 </p><p>　　D[j]+arcs[j][k]<D[k] </p><p>&l

13、t;b>　　則修改D[k]為</b></p><p>　　D[k]=D[j]+arcs[j][k] </p><p>　　(4) 重復(fù)（2）、（3）n-1次。由此求得v0到圖上其余各頂點(diǎn)得最短路徑。</p><p><b>　　程序說明</b></p><p>　　為了編程方便，以V0代表北京，V1代表

14、西安，V2代表沈陽，V3代表武漢。</p><p>　　首先輸入兩點(diǎn)之間的距離，即為矩陣中各元素的值。頂點(diǎn)到自身的權(quán)值用0表示，頂點(diǎn)間無邊時(shí)其對應(yīng)權(quán)值用-1表示。</p><p><b>　　功能實(shí)現(xiàn)</b></p><p><b>　　1）測試1：</b></p><p><b>　　假

15、設(shè)：</b></p><p>　　V0～V1之間距離是5；</p><p>　　V0～V2之間距離是8；</p><p>　　V0～V3之間距離是9；</p><p>　　V1～V2之間距離是2；</p><p>　　V1～V3之間距離是3；</p><p>　　V2～V3之間距離是

16、1。</p><p><b>　　如圖：</b></p><p><b>　　圖的鄰接矩陣如下：</b></p><p><b>　　運(yùn)行程序：</b></p><p>　　運(yùn)行程序出現(xiàn)如下界面，按照事先假設(shè)的數(shù)據(jù)輸入。</p><p>　　、輸入數(shù)據(jù)之

17、后，程序給出所求的鄰接矩陣、最短路徑、最短距離。</p><p><b>　　結(jié)果分析：</b></p><p>　　根據(jù)程序的運(yùn)行結(jié)果，我們可知：</p><p>　　、V0到V0的最短路徑的距離為：0</p><p>　　路徑：V0 V0</p><p>　　、V0到V1的最短路徑

18、的距離為：5</p><p>　　路徑：V0 V1</p><p>　　、V0到V2的最短路徑的距離為：7</p><p>　　路徑：V0 V1 V2</p><p>　　、V0到V3的最短路徑的距離為：8</p><p>　　路徑：V0 V1 V3</

19、p><p><b>　　2）測試2：</b></p><p><b>　　假設(shè)：</b></p><p>　　V0～V1之間不連通；</p><p>　　V0～V2之間不連通；</p><p>　　V0～V3之間距離是7；</p><p>　　V1～V2之

20、間距離是2；</p><p>　　V1～V3之間距離是5；</p><p>　　V2～V3之間距離是2。</p><p><b>　　如圖：</b></p><p><b>　　圖的鄰接矩陣如下：</b></p><p><b>　　運(yùn)行程序：</b>&

21、lt;/p><p>　　運(yùn)行程序出現(xiàn)如下界面，按照事先假設(shè)的數(shù)據(jù)輸入。</p><p>　　、輸入數(shù)據(jù)之后，程序給出所求的鄰接矩陣、最短路徑、最短距離。</p><p><b>　　結(jié)果分析：</b></p><p>　　根據(jù)程序的運(yùn)行結(jié)果，我們可知：</p><p>　　、V0到V0的最短路徑的距離

22、為：0</p><p>　　路徑：V0 V0</p><p>　　、V0到V1的最短路徑的距離為：11</p><p>　　路徑：V0 V3 V2 V1</p><p>　　、V0到V2的最短路徑的距離為：9</p><p>　　路徑：V0 V3

23、 V2</p><p>　　、V0到V3的最短路徑的距離為：7</p><p>　　路徑：V0 V3</p><p><b>　　3）測試3：</b></p><p><b>　　假設(shè)：</b></p><p>　　V0～V1之間不連通；</p>&

24、lt;p>　　V0～V2之間距離是3；</p><p>　　V0～V3之間距離是9；</p><p>　　V1～V2之間距離是2；</p><p>　　V1～V3之間距離是3；</p><p>　　V2～V3之間不連通。</p><p><b>　　如圖：</b></p>&l

25、t;p><b>　　圖的鄰接矩陣如下：</b></p><p><b>　　運(yùn)行程序：</b></p><p>　　運(yùn)行程序出現(xiàn)如下界面，按照事先假設(shè)的數(shù)據(jù)輸入。</p><p>　　、輸入數(shù)據(jù)之后，程序給出所求的鄰接矩陣、最短路徑、最短距離。</p><p><b>　　結(jié)果分析：

26、</b></p><p>　　根據(jù)程序的運(yùn)行結(jié)果，我們可知：</p><p>　　、V0到V0的最短路徑的距離為：0</p><p>　　路徑：V0 V0</p><p>　　、V0到V1的最短路徑的距離為：5</p><p>　　路徑：V0 V2 V1 &

27、lt;/p><p>　　、V0到V2的最短路徑的距離為：3</p><p>　　路徑：V0 V2 </p><p>　　、V0到V3的最短路徑的距離為：8</p><p>　　路徑：V0 V2 V1 V3</p><p><b>　　程序設(shè)計(jì)（二）

28、</b></p><p>　　編寫一個(gè)求素?cái)?shù)函數(shù)，把它書寫成一個(gè)動(dòng)態(tài)鏈接庫形式，并在主函數(shù)中調(diào)用它。嘗試把自己編寫的程序?qū)懗蓜?dòng)態(tài)鏈接庫和靜態(tài)鏈接庫形式，并比較以下三種EXE文件的大小。</p><p>　　A：調(diào)用靜態(tài)鏈接庫生成的EXE執(zhí)行文件。</p><p>　　B：調(diào)用動(dòng)態(tài)鏈接庫生成的EXE執(zhí)行文件。</p><p>　　C

29、：直接調(diào)用函數(shù)生成的EXE執(zhí)行文件。</p><p><b>　　1）、動(dòng)態(tài)連接</b></p><p>　?、佟⑿陆?xiàng)目 “Win32 Dynamic-Link Library” 項(xiàng)目名稱“sushu”,然后新建一個(gè)“sushu.cpp”文件，輸入以下代碼。</p><p>　　動(dòng)態(tài)連接DLL代碼：</p><p>　

30、　②、新建一個(gè)空的工程，項(xiàng)目名稱“sushu”。然后新建一個(gè)“sushu.cpp”文件，文件代碼如下。</p><p>　　然后把剛才項(xiàng)目生成的 .lib、.dll文件拷貝到該工程的debug目錄下。</p><p>　　動(dòng)態(tài)連接DLL調(diào)用代碼：</p><p><b>　　、運(yùn)行結(jié)果：</b></p><p><

31、b>　　2）、靜態(tài)連接</b></p><p>　　①、新建項(xiàng)目 “Win32 Dynamic-Link Library” 項(xiàng)目名稱“sushu”,然后新建一個(gè)“sushu.h”文件，輸入第一張圖片代碼。再新建一個(gè)“sushu.cpp”文件，輸入第二張圖片代碼。</p><p>　　靜態(tài)連接DLL代碼：</p><p>　?、凇⑿陆ㄒ粋€(gè)空的工程，項(xiàng)

32、目名稱“sushu”。然后新建一個(gè)“sushu.cpp”文件，文件代碼如下。</p><p>　　然后把剛才項(xiàng)目生成的 .lib、.dll文件拷貝到該工程的debug目錄下。</p><p>　　靜態(tài)連接DLL調(diào)用代碼：</p><p><b>　　③、運(yùn)行結(jié)果：</b></p><p><b>　　3）、結(jié)果

33、分析</b></p><p>　　靜態(tài)鏈接庫：lib中的指令被直接包含在最終生成的EXE文件中。</p><p>　　動(dòng)態(tài)鏈接庫：dll不必被包含在最終的EXE中，EXE文件執(zhí)行時(shí)可以動(dòng)態(tài)地引用和卸載DLL文件。</p><p>　　所以，調(diào)用靜態(tài)鏈接庫生成的EXE執(zhí)行文件要比調(diào)用動(dòng)態(tài)鏈接庫生成的EXE執(zhí)行文件大。</p><p>

34、;<b>　　課程設(shè)計(jì)總結(jié)</b></p><p>　　1、通過課程設(shè)計(jì)，我學(xué)會(huì)了如何建立圖的鄰接表，理解了圖的基本概念。</p><p>　　3、通過課程設(shè)計(jì)，我學(xué)會(huì)了如何編寫DLL函數(shù)。</p><p>　　4、能根據(jù)自己構(gòu)建的連通圖，利用Dijkstra算法求出從某個(gè)源點(diǎn)到其余各頂點(diǎn)的最短路徑。</p><p>　

35、　5、掌握了C++編程環(huán)境的基本調(diào)試方法，能熟練的使用可視化C++編程工具。</p><p><b>　　參考文獻(xiàn)</b></p><p>　　[1] 譚浩強(qiáng). C程序設(shè)計(jì)（第二版）[M]. 北京：清華大學(xué)出版社, 1999.</p><p>　　[2] 張青山. Dijkstra算法詳細(xì)講解[M]. 上海：復(fù)旦大學(xué)出版社, 2005.<

36、;/p><p>　　[3] 羅慧琴. VC++動(dòng)態(tài)鏈接庫(DLL)編程深入淺出[M]. 陜西：西安電子科技大學(xué)出版社, 2003.</p><p>　　[4] 嚴(yán)蔚敏, 吳偉民. 數(shù)據(jù)結(jié)構(gòu)[M]. 北京：清華大學(xué)出版社, 2005.</p><p>　　/* 用鄰接矩陣表示的圖的Dijkstra算法的源程序——*/</p><p>　　#incl

37、ude <stdio.h></p><p>　　#include <limits.h></p><p>　　#define Max INT_MAX</p><p>　　#define MAXVEX 4</p><p>　　#define FALSE 0</p><p>　　#define TRU

38、E 1</p><p>　　typedef struct</p><p><b>　　{ </b></p><p>　　int num; /* 圖的頂點(diǎn)個(gè)數(shù) */</p><p>　　char vexs[MAXVEX]; /*

39、頂點(diǎn)信息 */</p><p>　　float arcs[MAXVEX][MAXVEX]; /* 邊信息 */</p><p>　　}Tu; /* 定義結(jié)構(gòu)體Tu類型 */</p><p>　　void ShortestPath(Tu &G,int p[][MAXVEX],float D[])</p><p

40、><b>　　{ </b></p><p>　　int v,w,i,j;</p><p>　　float min;</p><p>　　int final[MAXVEX]; //final[v]為TRUE當(dāng)且僅當(dāng)v∈s,即已求得從v0到v的最短路徑</p><p>　　for(i=0;i<G.num;i

41、++)</p><p>　　{ final[i]=FALSE; </p><p>　　D[i]=G.arcs[0][i];</p><p>　　for(w=0;w<G.num;w++) p[i][w]=FALSE; /*設(shè)空路徑*/</p><p>　　if(D[i]!=-1) /*如果V0到Vi有直接路徑則置p[i

42、][0]和p[i][i]為1*/</p><p>　　{ p[i][0]=TRUE;</p><p>　　p[i][i]=TRUE;</p><p><b>　　}</b></p><p>　　}/*for語句結(jié)束*/</p><p>　　final[0]=TRUE; /* 初始化，表

43、示頂點(diǎn)v0在集合S中 */</p><p>　　for(i=1;i<G.num;i++) /*開始主循環(huán)，每次求得v0到某個(gè)v頂點(diǎn)的最短路徑，并加v到s集*/</p><p><b>　　{</b></p><p>　　min=Max; /* 初始化，表示最短距離min的初始值為無窮大 */</p>

44、<p>　　for(w=0;w<G.num;w++) /*在V-S中選出距離值最小頂點(diǎn)*/</p><p>　　if((!final[w]&&D[w]<min)&&(D[w]!=-1)) /*w頂點(diǎn)離v0頂點(diǎn)是更近*/</p><p>　　{ v=w; min=D[w]; } </p><p>　

45、　final[v]=TRUE; /*離v0最近的v加入S集*/</p><p>　　for(w=0;w<G.num;w++) /*更新當(dāng)前最短路徑及距離*/</p><p>　　if(G.arcs[v][w]!=-1) /*假如v到w之間相通，則執(zhí)行下一步*/</p><p>　　{if(!fina

46、l[w]&&((min+G.arcs[v][w]<D[w])||D[w]==-1)) /*修改D[w]和p[w]，w∈v-S*/</p><p>　　{D[w]=min+G.arcs[v][w]; /*修改路徑長度*/</p><p>　　for(j=0;j<G.num;j++)p[w][j]=p[v][j]; /*修

47、改路徑為經(jīng)過v到達(dá)w*/</p><p>　　p[w][w]=TRUE;}</p><p>　　}/*if結(jié)束*/ </p><p>　　}/*for結(jié)束*/</p><p>　　}/*ShortestPath結(jié)束*/</p><p>　　void main()</p><p><b>

48、;　　{ </b></p><p>　　printf("\n*************************************************\n");/*輸出提示信息*/</p><p>　　printf(" V0 代表 北京\n");</p><p>　　pri

49、ntf(" V1 代表 西安\n");</p><p>　　printf(" V2 代表 沈陽\n");</p><p>　　printf(" V3 代表 武漢\n");</p><p>　　printf(&quo

50、t;*************************************************\n\n");</p><p><b>　　int i,j;</b></p><p><b>　　Tu G;</b></p><p>　　float D[MAXVEX]; /*D(v)為v0

51、到v的路徑長度*/</p><p>　　int p[MAXVEX][MAXVEX]; /*p(v)記錄v0到v的最短路徑，若p[v][w]為TRUE，則w是從v0到v當(dāng)前求得最短路徑上的頂點(diǎn)*/</p><p>　　G.num=4; /*一共有四個(gè)城市*/</p><p>　　for(i=0;i<G.num;i++) /*

52、for循環(huán)輸入四個(gè)城市之間的距離*/</p><p><b>　　{</b></p><p>　　for(j=0;j<G.num;j++)</p><p><b>　　{</b></p><p>　　if(i==j) /*假如i等于j，表示該城市到自身的距離，置為0*/&l

53、t;/p><p>　　G.arcs[i][j]=0;</p><p><b>　　else{</b></p><p><b>　　if(j>i)</b></p><p><b>　　{</b></p><p>　　printf(" 請

54、輸入");</p><p>　　printf("V%d",i); </p><p>　　printf("到");</p><p>　　printf("V%d",j); </p><p>　　printf("的距離 (不通請輸入-1)\n "

55、);</p><p>　　scanf("%f",&G.arcs[i][j]);</p><p>　　G.arcs[j][i]=G.arcs[i][j]; /*該圖為無向圖，所以i到j(luò)的距離即為j到i的距離*/</p><p>　　}/*if結(jié)束*/ </p><p>　　} /*else結(jié)束*/ &l

56、t;/p><p>　　}/*for結(jié)束*/ </p><p>　　}/*for結(jié)束*/ </p><p>　　ShortestPath(G,p,D); /*代入數(shù)據(jù)求解最短距離*/ </p><p>　　printf("\n以鄰接矩陣的形式表示圖為：\n"); /*以鄰接矩陣形式輸出圖*/</

57、p><p>　　for(i=0;i<G.num;i++) </p><p>　　{ for(j=0;j<G.num;j++)</p><p>　　printf("%12.0f",G.arcs[i][j]);</p><p>　　printf("\n");</p>

58、<p><b>　　}</b></p><p>　　printf("\nV0到其它各頂點(diǎn)的路徑表示為：\n"); /*輸出V0到其它各頂點(diǎn)的路徑*/</p><p>　　for(i=0;i<G.num;i++) </p><p>　　{ for(j=0;j<G.num;j++)

59、</p><p>　　printf("%12d",p[i][j]);</p><p>　　printf("\n");</p><p><b>　　}</b></p><p>　　printf("\nV0到其它各頂點(diǎn)的最短距離為：\n"); /*輸出V0到其它

60、各頂點(diǎn)的最短距離*/</p><p>　　for(i=0;i<G.num;i++) </p><p>　　{ printf(" V0 到");</p><p>　　printf(" V%d ",i);</p><p>　　printf("的最短路

61、徑的距離為：");</p><p>　　printf("%.0f\n",D[i]);</p><p><b>　　}</b></p><p>　　printf("\n \n");</p><p>