軟件基礎課程設計--從某個源點到其余各頂點的最短路徑

上傳人：奔*** IP屬地：河北更新時間：2024-03-01 格式：doc 頁數(shù)：23 大?。?89.50KB 人氣指數(shù)：12 舉報 版權申訴

已閱讀1頁，還剩22頁未讀，繼續(xù)免費閱讀

版權說明：本文檔由用戶提供并上傳，收益歸屬內容提供方，若內容存在侵權，請進行舉報或認領

文檔簡介

1、　　軟件設計基礎課程設計　　題目：從某個源點到其余各頂點的最短路徑 　　學院：信息與通信工程學院 　　專業(yè)：通信工程專業(yè)

2、 　　學生姓名： 　　班級/學號： 　　指導老師：

3、 　　起止時間： 2013-9-22 至 2013-11-6 　　摘要 　　本次課程設計的問題：假設西安、北京、沈陽、武漢4個城市構成小型交通網，4個城市表示圖的4個頂點，它們構成了無

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

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

6、;　　任務書1　　摘要2　　目錄3　　正文4　　一、應用迪科斯徹（Dijkstra）算法計算最短路徑4&

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

8、t;　　七、課程設計總結16　　參考文獻17　　源代碼18　　應用迪科斯徹（Dijkstra）算法計算最短路徑　　假設西安、北京、沈陽、武漢4個城市構成小型交通網，4個

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

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

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

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

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

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

15、設：　　V0～V1之間距離是5；　　V0～V2之間距離是8；　　V0～V3之間距離是9；　　V1～V2之間距離是2；　　V1～V3之間距離是3；　　V2～V3之間距離是

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

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

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

19、p>　　2）測試2：　　假設：　　V0～V1之間不連通；　　V0～V2之間不連通；　　V0～V3之間距離是7；　　V1～V2之

20、間距離是2；　　V1～V3之間距離是5；　　V2～V3之間距離是2。　　如圖：　　圖的鄰接矩陣如下：　　運行程序：&

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

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

23、 V2　　、V0到V3的最短路徑的距離為：7　　路徑：V0 V3　　3）測試3：　　假設：　　V0～V1之間不連通；&

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

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

26、　　根據(jù)程序的運行結果，我們可知：　　、V0到V0的最短路徑的距離為：0　　路徑：V0 V0　　、V0到V1的最短路徑的距離為：5　　路徑：V0 V2 V1 &

27、lt;/p>　　、V0到V2的最短路徑的距離為：3　　路徑：V0 V2 　　、V0到V3的最短路徑的距離為：8　　路徑：V0 V2 V1 V3　　程序設計（二）

28、　　編寫一個求素數(shù)函數(shù)，把它書寫成一個動態(tài)鏈接庫形式，并在主函數(shù)中調用它。嘗試把自己編寫的程序寫成動態(tài)鏈接庫和靜態(tài)鏈接庫形式，并比較以下三種EXE文件的大小。　　A：調用靜態(tài)鏈接庫生成的EXE執(zhí)行文件。　　B：調用動態(tài)鏈接庫生成的EXE執(zhí)行文件。　　C

29、：直接調用函數(shù)生成的EXE執(zhí)行文件。　　1）、動態(tài)連接　?、?、新建項目 “Win32 Dynamic-Link Library” 項目名稱“sushu”,然后新建一個“sushu.cpp”文件，輸入以下代碼。　　動態(tài)連接DLL代碼：

30、?、凇⑿陆ㄒ粋€空的工程，項目名稱“sushu”。然后新建一個“sushu.cpp”文件，文件代碼如下。　　然后把剛才項目生成的 .lib、.dll文件拷貝到該工程的debug目錄下。　　動態(tài)連接DLL調用代碼：　　、運行結果：<

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

32、目名稱“sushu”。然后新建一個“sushu.cpp”文件，文件代碼如下。　　然后把剛才項目生成的 .lib、.dll文件拷貝到該工程的debug目錄下。　　靜態(tài)連接DLL調用代碼：　　③、運行結果：　　3）、結果

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

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

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

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

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

38、E 1　　typedef struct　　{ 　　int num; /* 圖的頂點個數(shù) */　　char vexs[MAXVEX]; /*

39、頂點信息 */　　float arcs[MAXVEX][MAXVEX]; /* 邊信息 */　　}Tu; /* 定義結構體Tu類型 */　　void ShortestPath(Tu &G,int p[][MAXVEX],float D[])<p

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

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

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

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

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

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

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

47、改路徑為經過v到達w*/　　p[w][w]=TRUE;}　　}/*if結束*/ 　　}/*for結束*/　　}/*ShortestPath結束*/　　void main()

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

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

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

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

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

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

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

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

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

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

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

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

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

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

眾賞文庫> 全部分類> 畢業(yè)設計

溫馨提示

1. 本站所有資源如無特殊說明，都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
2. 本站的文檔不包含任何第三方提供的附件圖紙等，如果需要附件，請聯(lián)系上傳者。文件的所有權益歸上傳用戶所有。
3. 本站RAR壓縮包中若帶圖紙，網頁內容里面會有圖紙預覽，若沒有圖紙預覽就沒有圖紙。
4. 未經權益所有人同意不得將文件中的內容挪作商業(yè)或盈利用途。
5. 眾賞文庫僅提供信息存儲空間，僅對用戶上傳內容的表現(xiàn)方式做保護處理，對用戶上傳分享的文檔內容本身不做任何修改或編輯，并不能對任何下載內容負責。
6. 下載文件中如有侵權或不適當內容，請與我們聯(lián)系，我們立即糾正。
7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

軟件基礎課程設計--從某個源點到其余各頂點的最短路徑

文檔簡介

溫馨提示

最新文檔

評論

軟件基礎課程設計--從某個源點到其余各頂點的最短路徑

文檔簡介

溫馨提示

最新文檔

評論

免費下載