算法課程設(shè)計--校園導(dǎo)航系統(tǒng)

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

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

版權(quán)說明：本文檔由用戶提供并上傳，收益歸屬內(nèi)容提供方，若內(nèi)容存在侵權(quán)，請進行舉報或認(rèn)領(lǐng)

文檔簡介

1、　　摘要　　本次課程設(shè)計主要核心為利用迪杰斯特拉算法實現(xiàn)無向圖的最短路徑的計算和求解。要求理解迪杰斯特拉算法的具體實現(xiàn)流程、學(xué)會正確使用該算法求解實際問題。本次課程設(shè)計具體內(nèi)容是：為自己學(xué)校建立一個校園導(dǎo)航系統(tǒng)。該系統(tǒng)應(yīng)該具有：查詢?nèi)我鈨牲c最短路徑以及查詢?nèi)我庖稽c到其他各點的最短路徑。　　本程序要求

2、結(jié)合最短路徑迪杰斯特拉算法以及相應(yīng)的數(shù)據(jù)結(jié)構(gòu)的定義和使用，實現(xiàn)一個最短路徑算法的簡單應(yīng)用。本文主要包括的函數(shù)模塊有：數(shù)據(jù)結(jié)構(gòu)定義、無向圖的建立、導(dǎo)航圖建立、最短路徑求解及主函數(shù)模塊。還有運行調(diào)試過程的截圖，最后附上程序清單，以供查閱。　　本課程設(shè)計是對書本知識的簡單應(yīng)用，以此培養(yǎng)大家用書本知識解決實際問題的能力；培養(yǎng)實際工作所需要的動手能力；培養(yǎng)以科學(xué)理論和工程上能力的技術(shù)，規(guī)范地開發(fā)大型、復(fù)雜

3、、高質(zhì)量的應(yīng)用軟件和系統(tǒng)軟件。　　關(guān)鍵字：校園導(dǎo)航，迪杰斯特拉算法，最短路徑，算法設(shè)計，數(shù)據(jù)結(jié)構(gòu)　　目錄　　摘要I　　1問題描述1

4、;　　2方案設(shè)計2　　2.1 數(shù)據(jù)結(jié)構(gòu)定義模塊2　　2.2 功能模塊定義2　　2.2.1 無向圖構(gòu)造模塊2　　2.2.2 導(dǎo)航圖建立模塊2　　2.2.

5、3 求最短路徑模塊3　　2.2.4 主菜單3　　3 流程圖4　　3.1 系統(tǒng)運行流程圖4　　3.2 迪杰斯特拉算法流程圖5　　4 功能模塊代碼實現(xiàn)6

6、　　4.1 創(chuàng)建無向圖函數(shù)6　　4.2導(dǎo)航菜單生成7　　4.3最短路徑求解函數(shù)8　　5 運行調(diào)試11　　5.1查詢系統(tǒng)導(dǎo)航界面11　　5.2兩點最短距離導(dǎo)航11

7、　　5.3某點到其他所有點最短距離12　　5.4退出系統(tǒng)12　　6程序設(shè)計總結(jié)13　　7 參考文獻14　　附錄程序清單15　　問題描述

8、;　　這是一個最短路徑算法的簡單應(yīng)用，體現(xiàn)了理論與實際的結(jié)合。在完成本系統(tǒng)過程中，應(yīng)用所學(xué)知識解決具體的實際問題。　　根據(jù)本設(shè)計要求，首先應(yīng)該根據(jù)本學(xué)校的具體實際，建立校園平面圖。然后根據(jù)該圖建立無向圖的鄰接矩陣，矩陣的值表示兩點之間的實際距離。最后根據(jù)用戶請求調(diào)用迪杰斯特拉算法，并輸出相應(yīng)的路徑信息。　　該系統(tǒng)還應(yīng)該設(shè)計可視化導(dǎo)航

9、鍵面，方便用戶使用。根據(jù)本課程設(shè)計要求，本系統(tǒng)應(yīng)該具備如下功能：　　1、查詢?nèi)我鈨牲c間的最短路徑（包括途經(jīng)地點以及最短距離）；　　2、查詢?nèi)我庖稽c到其他各點的最短路徑（包括途經(jīng)地點以及最短距離）；　　3、能完成連續(xù)的查詢工作；　　4、用戶查詢完后能方便的退出程序系統(tǒng)。&l

10、t;/p>　　方案設(shè)計　　2.1 數(shù)據(jù)結(jié)構(gòu)定義模塊　　本模塊定義了導(dǎo)航圖中各個節(jié)點的基本結(jié)構(gòu)類型，主要采用鄰接矩陣的存儲結(jié)構(gòu)[1]來真實反映各節(jié)點到其他所有節(jié)點的路徑長度（權(quán)值大小）。　　其數(shù)據(jù)結(jié)構(gòu)定義為：&

11、lt;/p>　　typedef struct　　{　　char* vexs[MAX_V]; //頂點向量　　int arcs[MAX_V][MAX_V];//鄰接矩陣　　int vexnum,a

12、rcnum;//圖的當(dāng)前頂點數(shù)和弧數(shù)　　}MGraph;　　2.2 功能模塊定義　　2.2.1 無向圖構(gòu)造模塊　　根據(jù)實際情況設(shè)計學(xué)校平面圖（至少包含10個地點），并采用鄰接矩陣實現(xiàn)對該平面圖節(jié)點及權(quán)值信息的存儲[3]。包括：各定

13、點的名稱（地點名），各個節(jié)點到其他所有節(jié)點的真實路徑長度（賦權(quán)值）[4]。即對無向圖兩點間的邊值賦值。　　本課程設(shè)計中涉及地點編號及信息如下：　　(1) 南門 (2) 行政樓 (3) 學(xué)生會堂 　　(4) C 區(qū) (5) 靜

14、明湖 (6) 圖書館 　　(7) 分析測試中心 (8) 第二教學(xué)樓 (9) 羽毛球場 　　(10) 勵志樓 (11) 學(xué)生公寓中心 (12) 食堂區(qū) 　　(13) 醫(yī)務(wù)室 (

15、14) 凌云樓 (15) 籃球場 　　(16) 生化樓 (17) 東門 (18) 文德樓 　　(19) 排球場 (20) 第一教學(xué)樓 (21) 學(xué)生活動中心 　　(22) 足球場

16、 (23) 北門 (24) 西苑 　　(25) 學(xué)生洗滌中心 (26) 開水房 (27) 自助服務(wù)點　　2.2.2 導(dǎo)航圖建立模塊　　根據(jù)課程設(shè)計功能要求設(shè)計人性化的導(dǎo)航界面，方便用戶根據(jù)自己實際需要查詢的信息選擇相應(yīng)的

17、菜單，完成導(dǎo)航功能。　　主界面中應(yīng)包括的選項有：　　(1) 兩點最短距離導(dǎo)航 　　(2) 某點到其他所有點的最短距離 　　(3) 退出導(dǎo)航系統(tǒng) 　　選擇功能號后，還應(yīng)提示用戶輸入待查地點編

18、號信息。　　2.2.3 求最短路徑模塊　　本模塊的基本思想是采用迪杰斯特拉算法[2]求最短路徑，是本校園導(dǎo)航系統(tǒng)的核心模塊，求兩點間的最短路徑與求一點到其他所有點最短路徑兩個子功能均是在最短路徑算法模塊的基礎(chǔ)上進行調(diào)用，進而實現(xiàn)導(dǎo)航功能。　　2.2.4 主函數(shù)模塊

19、主函數(shù)模塊是整個程序的入口，包括對各變量、數(shù)據(jù)結(jié)構(gòu)以及要使用的函數(shù)的聲明等。　　主函數(shù)中其他功能函數(shù)調(diào)用有一定的順序。首先調(diào)用導(dǎo)航圖的建立函數(shù)，構(gòu)建可視化導(dǎo)航菜單；然后獲取用戶的輸入，并根據(jù)輸入調(diào)用相應(yīng)的功能函數(shù)，實現(xiàn)導(dǎo)航系統(tǒng)的功能。　　3 流程圖　　3.1 系統(tǒng)運行流程

20、圖　　3.2 迪杰斯特拉算法流程圖　　圖3.2 迪杰斯特拉算法流程圖　　4 功能模塊代碼實現(xiàn)　　4.1 創(chuàng)建無向圖函數(shù)　　int CreateUDN(MGraph &G)

21、　函數(shù)描述：主要將每個節(jié)點進行命名、每個頂點到其他所有定點的路徑值用鄰接矩陣進行存儲[1]。　　例：　　G.vexs[0] = "南門"; 　　作用：使0號定點命名為“南門”； 　　G.arcs[0][1] = G

22、.arcs[1][0] =20;　　作用：使0號節(jié)點到1號節(jié)點的路徑賦值為20，應(yīng)為是無向圖，所以1號節(jié)點到0號節(jié)點的路徑長度也應(yīng)賦值為20。　　具體賦值如下：　　G.arcs[0][1] = G.arcs[1][0] =20;

23、G.arcs[0][5] = G.arcs[5][0] =100;　　G.arcs[0][6] = G.arcs[6][0] =80;　　G.arcs[1][2] = G.arcs[2][1] =50;　　G.arcs[2][3] = G.arcs[3][2] =200; <

24、p>　　G.arcs[2][4] = G.arcs[4][2] =50;　　G.arcs[3][4] = G.arcs[4][3] =200;　　G.arcs[3][23] = G.arcs[23][3]=1500;　　G.arcs[4][5] = G.arcs[5][4] =20;

25、;　　G.arcs[5][6] = G.arcs[6][5] =80; 　　G.arcs[6][7] = G.arcs[7][6] =80;　　G.arcs[7][8] = G.arcs[8][7] =50;　　G.arcs[7][9] = G.arcs[9][7] =60; &l

26、t;/p>　　G.arcs[8][10] = G.arcs[10][8] =220;　　G.arcs[8][18] = G.arcs[18][8] =200; 　　G.arcs[8][21] = G.arcs[21][8] =130;　　G.arcs[10][11]= G.arcs[

27、11][10] =150; 　　G.arcs[10][25]= G.arcs[25][10] =120;　　G.arcs[11][12]= G.arcs[12][11] =120;　　G.arcs[12][13]= G.arcs[13][12] =20;　　G.arcs[

28、12][26]= G.arcs[26][12] =150;　　G.arcs[13][14]= G.arcs[14][13] =50;　　G.arcs[13][15]= G.arcs[15][13] =100;　　G.arcs[13][17]= G.arcs[17][13] =70;<

29、p>　　G.arcs[13][20]= G.arcs[20][13] =30;　　G.arcs[13][24]= G.arcs[24][13] =20;　　G.arcs[14][15]= G.arcs[15][14] =70;　　G.arcs[14][16]= G.arcs[16][14] =100;<

30、;/p>　　G.arcs[15][16]= G.arcs[16][15] =60; 　　G.arcs[15][17]= G.arcs[17][15] =50;　　G.arcs[17][18]= G.arcs[18][17] =80;　　G.arcs[17][19]= G.arcs[1

31、9][17] =120;　　G.arcs[18][19]= G.arcs[19][18] =110; 　　G.arcs[18][20]= G.arcs[20][18] =50;　　G.arcs[19][21]= G.arcs[21][19] =100;　　G.arcs[1

32、9][22]= G.arcs[22][19] =80; 　　G.arcs[20][24]= G.arcs[24][20] =20;　　G.arcs[25][26]= G.arcs[26][25] =30;　　導(dǎo)航菜單生成　　void

33、menu()　　函數(shù)描述：輸出各個節(jié)點的編號，及本系統(tǒng)所提供的查詢方式，方便導(dǎo)航。　　具體導(dǎo)航菜單設(shè)計如下：　　void menu()　　{　　printf("☆ ☆ ☆ ☆ ☆ ☆

34、 ☆ ☆ ☆ ☆ 導(dǎo)航主菜單 ☆ ☆ ☆ ☆ ☆ ☆ ☆ ☆ ☆ \n");　　printf("☆ (1) 南門 (2) 行政樓 (3) 學(xué)生會堂 ☆ \n");　　printf("☆ (4) C 區(qū) (5) 靜明湖

35、 (6) 圖書館 ☆ \n");　　printf("☆ (7) 分析測試中心 (8) 第二教學(xué)樓 (9) 羽毛球場 ☆ \n");　　printf("☆ (10) 勵志樓 (11) 學(xué)生公寓中心 (12) 食堂區(qū)

36、 ☆ \n");　　printf("☆ (13) 醫(yī)務(wù)室 (14) 凌云樓 (15) 籃球場 ☆ \n");　　printf("☆ (16) 生化樓 (17) 東門 (18) 文德樓 ☆ \

37、n");　　printf("☆ (19) 排球場 (20) 第一教學(xué)樓 (21) 學(xué)生活動中心 ☆ \n");　　printf("☆ (22) 足球場 (23) 北門 (24) 西苑 ☆ \n");<

38、/p>　　printf("☆ (25) 學(xué)生洗滌中心 (26) 開水房 (27) 自助服務(wù)點 ☆ \n");　　printf("☆ ☆ ☆ ☆ ☆ ☆ ☆ ☆ ☆ ☆ ☆ ☆ ☆ ☆ ☆ ☆ ☆ ☆ ☆ ☆ ☆ ☆ ☆ \n\n");　　printf

39、("請選擇導(dǎo)航功能：\n");　　printf("≈≈≈≈≈≈≈≈≈≈≈≈≈≈≈≈≈≈≈≈\n");　　printf("≈ (1) 兩點最短距離導(dǎo)航 ≈\n");　　printf("≈ (2) 某點到其他所有點的

40、最短距離 ≈\n");　　printf("≈ (3) 退出導(dǎo)航系統(tǒng) ≈\n");　　printf("≈≈≈≈≈≈≈≈≈≈≈≈≈≈≈≈≈≈≈≈\n");　　}<

41、;p>　　最短路徑求解函數(shù)　　void ShortPath(MGraph &G,int v0,int p[MAX_V][MAX_V],int d[])　　函數(shù)描述：用Dijkstra算法求無向網(wǎng)G的V0定點到其余定點V的最短路徑P[v]及其帶權(quán)長度D[v][5]。若P[v][w]為True，則w是從V0

42、到V當(dāng)前求得最短路徑上的頂點。Final[v]為True當(dāng)且僅當(dāng)V∈S，即已經(jīng)求得從V0到V的最短路徑。　　利用迪杰斯特拉算法設(shè)計最短路徑算法如下：　　void ShortPath(MGraph &G,int v0,int p[MAX_V][MAX_V],int d[])　　{ &

43、lt;/b>　　int v,w,i,j,min;　　int final[MAX_V];　　int k=1;　　for(v=0;v<G.vexnum;++v)　　{

44、//初始化　　final[v]=0;　　d[v]=G.arcs[v0-1][v];　　for(w=0;w<G.vexnum;++w)　　p[v][w]=0;　　if(d[v]<INFINITY)&l

45、t;/p>　　{　　p[v][v0-1]=1;　　p[v][v]=1;　　}　　}　　d

46、[v0-1]=0;　　final[v0-1]=1;　　have[0]=v0-1;　　for(i=1;i<G.vexnum;++i)　　{//其余的vexnum-1個頂點　　min=INFINITY;&

47、lt;p>　　for(w=0;w<G.vexnum;++w)　　if(!final[w])　　if(d[w]<min) //如有W點離更近　　{　　v=w;

48、　　min=d[w];　　}　　final[v]=1;　　have[k]=v;　　k++;　　f

49、or(w=0;w<G.vexnum;++w)//更新當(dāng)前最短路徑及距離　　if(!final[w]&&(min+G.arcs[v][w]<d[w]))　　{　　d[w]=min+G.arcs[v][w];

50、　for(j=0;j<G.vexnum;j++)　　p[w][j]=p[v][j];　　p[w][w]=1;　　}　　}　　}&l

51、t;/b>　　5 運行調(diào)試　　查詢系統(tǒng)導(dǎo)航界面　　圖5.1 查詢系統(tǒng)導(dǎo)航截圖　　兩點最短距離導(dǎo)航　　圖5.

52、2 兩點最短距離導(dǎo)航截圖　　某點到其他所有點最短距離　　圖5.3 任意點到其他各點最短路徑截圖　　退出系統(tǒng)　　圖5.4 退出系統(tǒng)截圖　　程序設(shè)計總結(jié)

53、　　7 參考文獻　　[1］《數(shù)據(jù)結(jié)構(gòu)》（C語言版），嚴(yán)蔚敏，清華大學(xué)出版社，2005．　　[2］《算法設(shè)計與分析》，王曉東主編，清華大學(xué)出版社，2005　　[3］汪詩林等譯，《數(shù)據(jù)結(jié)構(gòu)、算法與應(yīng)用》，（美）Sartaj Sahni著

54、，機械工業(yè)出版社， 1999　　[4］《數(shù)據(jù)結(jié)構(gòu)與算法分析》，CLIFFORD A. SHAFFER著，張銘、劉曉丹譯，電子工業(yè)出版社，1998　　[5] 《計算機算法設(shè)計與分析》，王曉東，電子工業(yè)出版社，2007　　[6] 《數(shù)據(jù)結(jié)構(gòu)與算法使用教程》，劉玉龍，電子工業(yè)大學(xué)出版社，2009

55、　　附錄程序清單　　#include <stdio.h>　　#include <stdlib.h>　　#include <string.h>　　#define MAX_V 30

56、 //最大頂點個數(shù)　　#define INFINITY 32767 //最大值　　typedef struct　　{　　char* vexs[MAX_V]; //頂點向量<

57、p>　　int arcs[MAX_V][MAX_V];//鄰接矩陣　　int vexnum,arcnum;//圖的當(dāng)前頂點數(shù)和弧數(shù)　　}MGraph;　　int have[30];　　void CreateUDN(MGraph

58、&G);//創(chuàng)建導(dǎo)航圖函數(shù)聲明　　void ShortPath(MGraph &G,int v0,int p[MAX_V][MAX_V],int d[]);//最短路徑導(dǎo)航函數(shù)聲明　　void menu();//導(dǎo)航菜單函數(shù)聲明　　void main()<p

59、>　　{　　MGraph G;　　int v0,i,end,j;　　int P[MAX_V][MAX_V];　　int D[MAX_V];　　in

60、t choice,choice1;　　printf("≈≈≈≈≈≈≈≈≈≈≈≈≈≈≈≈≈≈≈≈≈≈≈≈≈≈≈≈≈≈≈≈≈≈\n");　　printf("\n≈≈ 歡迎光臨攀枝花學(xué)院，祝旅程愉快！ ≈≈\n");　　printf(&q

61、uot;\n≈≈ 攀枝花學(xué)院校園導(dǎo)游系統(tǒng)為你服務(wù)！ ≈≈\n");　　printf("\n≈≈≈≈≈≈≈≈≈≈≈≈≈≈≈≈≈≈≈≈≈≈≈≈≈≈≈≈≈\n\n");CreateUDN(G);　　while(1)<p

62、>　　{ 　　menu();　　scanf("%d",&choice);　　switch(choice)　　{</p&

63、gt;　　case 1:　　{　　while(1)　　{　　printf("分別輸入起點

64、和終點代號以空格分開\n");　　scanf("%d%d",&v0,&end);　　ShortPath(G,v0,P,D);　　printf("最短路徑:\n ");　　for(i=0;i<G.vex

65、num;i++)　　{ 　　if(P[end-1][have[i]]==1)　　printf("-->%s",G.vexs[have[i]]);　　}

66、;　　printf("\n路徑長度:%d\n",D[end-1]);　　printf("^_^ 本次導(dǎo)航結(jié)束:\n1.繼續(xù)導(dǎo)航 2.返回主菜單\n");　　scanf("%d",&choice1);　　if(cho

67、ice1==2) 　　break;　　}　　}　　break;<b&

68、gt;　　case 2:　　{　　printf("請輸入出發(fā)點：");　　scanf("%d",&v0);　　ShortPath(G,v0,P,D);</p&g

69、t;　　printf("%s到其他所有點的最短路徑為：\n",G.vexs[v0-1]);　　for(i=0;i<G.vexnum;i++)　　{　　for(j=0;j<G.vexnum;j++)&

70、lt;p>　　if(P[i][have[j]]==1)　　printf("-->%s",G.vexs[have[j]]);　　printf("\n路徑長度:%d\n",D[i]);　　}&

71、lt;p>　　}　　break;　　case 3:　　break;　　default:</

72、b>　　printf("選擇錯誤，請重新輸入！\n");　　}　　if(choice==3)　　{　　printf(&qu

73、ot;歡迎再次使用校園導(dǎo)航系統(tǒng)，回車鍵退出。^_^\n");　　getchar();　　getchar();　　break;　　}<b&g

74、t;　　}　　}　　void CreateUDN(MGraph &G)　　{//采用數(shù)組(鄰接矩陣)表示法,構(gòu)造無向網(wǎng)G.　　int i = 0,j=0;　　G.

75、vexnum = 27; 　　G.arcnum = 51;　　G.vexs[0] = "南門"; G.vexs[1] = "行政樓"; G.vexs[2] = "學(xué)生會堂";　　G.vexs[3] = "C區(qū)&q

76、uot;; G.vexs[4] = "靜明湖"; G.vexs[5] = "圖書館";　　G.vexs[6] = "分析測試中心"; G.vexs[7] = "第二教學(xué)樓"; G.vexs[8] = "羽毛球場";　　G.

77、vexs[9] = "勵志樓"; G.vexs[10] = "學(xué)生公寓中心";G.vexs[11] ="食堂區(qū)";　　G.vexs[12] = "醫(yī)務(wù)室"; G.vexs[13] = "凌云樓"; G.vexs[14] = "籃球場";</

78、p>　　G.vexs[15] = "生化樓"; G.vexs[16] = "東門"; G.vexs[17] = "文德樓";　　G.vexs[18] = "排球場"; G.vexs[19] = "第一教學(xué)樓"; G.vexs[20]

79、= "學(xué)生活動中心";　　G.vexs[21] = "足球場"; G.vexs[22] = "北門"; G.vexs[23] = "西苑";　　G.vexs[24] = "學(xué)生洗滌中心";G.vexs[25] = "開水房

80、"; G.vexs[26] = "自助服務(wù)點";　　for(i=0;i<G.vexnum;i++) //初始化路徑長度　　for(j=0;j<G.vexnum;j++)　　{<

81、;b>　　if(i==j)　　G.arcs[i][j]=0;　　else 　　G.arcs[i][j]=INFINITY;　　}

82、　　//為每一條邊賦權(quán)　　G.arcs[0][1] = G.arcs[1][0] =20;　　G.arcs[0][5] = G.arcs[5][0] =100;　　G.arcs[0][6] = G.arcs[6][0] =80;

83、　　G.arcs[1][2] = G.arcs[2][1] =50;　　G.arcs[2][3] = G.arcs[3][2] =200; 　　G.arcs[2][4] = G.arcs[4][2] =50;　　G.arcs[3][4] = G.arcs[4][3] =200;&l

84、t;p>　　G.arcs[3][23] = G.arcs[23][3]=1500;　　G.arcs[4][5] = G.arcs[5][4] =20;　　G.arcs[5][6] = G.arcs[6][5] =80; 　　G.arcs[6][7] = G.arcs[7][6] =80;</p&

85、gt;　　G.arcs[7][8] = G.arcs[8][7] =50;　　G.arcs[7][9] = G.arcs[9][7] =60; 　　G.arcs[8][10] = G.arcs[10][8] =220;　　G.arcs[8][18] = G.arcs[18][8] =2

86、00; 　　G.arcs[8][21] = G.arcs[21][8] =130;　　G.arcs[10][11]= G.arcs[11][10] =150; 　　G.arcs[10][25]= G.arcs[25][10] =120;　　G.arcs[11][12]=

87、 G.arcs[12][11] =120;　　G.arcs[12][13]= G.arcs[13][12] =20;　　G.arcs[12][26]= G.arcs[26][12] =150;　　G.arcs[13][14]= G.arcs[14][13] =50;　　G

88、.arcs[13][15]= G.arcs[15][13] =100;　　G.arcs[13][17]= G.arcs[17][13] =70;　　G.arcs[13][20]= G.arcs[20][13] =30;　　G.arcs[13][24]= G.arcs[24][13] =20;

89、　　G.arcs[14][15]= G.arcs[15][14] =70;　　G.arcs[14][16]= G.arcs[16][14] =100;　　G.arcs[15][16]= G.arcs[16][15] =60; 　　G.arcs[15][17]= G.arcs[17][15]

90、=50;　　G.arcs[17][18]= G.arcs[18][17] =80;　　G.arcs[17][19]= G.arcs[19][17] =120;　　G.arcs[18][19]= G.arcs[19][18] =110; 　　G.arcs[18][20]=

91、G.arcs[20][18] =50;　　G.arcs[19][21]= G.arcs[21][19] =100;　　G.arcs[19][22]= G.arcs[22][19] =80; 　　G.arcs[20][24]= G.arcs[24][20] =20;　　G.

92、arcs[25][26]= G.arcs[26][25] =30;　　}　　void ShortPath(MGraph &G,int v0,int p[MAX_V][MAX_V],int d[])　　{ //迪杰斯特拉發(fā)求最短路徑<p

93、>　　int v,w,i,j,min;　　int final[MAX_V];　　int k=1;　　for(v=0;v<G.vexnum;++v)　　{//初始化

94、　　final[v]=0;　　d[v]=G.arcs[v0-1][v];　　for(w=0;w<G.vexnum;++w)　　p[v][w]=0;　　if(d[v]<INFINITY)<b&g

95、t;　　{　　p[v][v0-1]=1;　　p[v][v]=1;　　}　　}　　d[v0-1]=0;<p

96、>　　final[v0-1]=1;　　have[0]=v0-1;　　for(i=1;i<G.vexnum;++i)　　{//其余的vexnum-1個頂點　　min=INFINITY;　　for(w=0;w<G.v

97、exnum;++w)　　if(!final[w])　　if(d[w]<min) //如有W點離更近　　{　　v=w;　　min=d

98、[w];　　}　　final[v]=1;　　have[k]=v;　　k++;　　for(w=0;w<G.vexnum;++w)/

99、/更新當(dāng)前最短路徑及距離　　if(!final[w]&&(min+G.arcs[v][w]<d[w]))　　{　　d[w]=min+G.arcs[v][w];　　for(j=0;j<G.vexnum;j++

100、)　　p[w][j]=p[v][j];　　p[w][w]=1;　　}　　}　　}<p&

101、gt;　　void menu()　　{　　printf("☆ ☆ ☆ ☆ ☆ ☆ ☆ ☆ ☆ ☆ 導(dǎo)航主菜單 ☆ ☆ ☆ ☆ ☆ ☆ ☆ ☆ ☆ \n");　　printf("☆ (1) 南門 (2) 行政樓

102、 (3) 學(xué)生會堂 ☆ \n");　　printf("☆ (4) C 區(qū) (5) 靜明湖 (6) 圖書館 ☆ \n");　　printf("☆ (7) 分析測試中心 (8) 第二教學(xué)樓 (9)

103、羽毛球場 ☆ \n");　　printf("☆ (10) 勵志樓 (11) 學(xué)生公寓中心 (12) 食堂區(qū) ☆ \n");　　printf("☆ (13) 醫(yī)務(wù)室 (14) 凌云樓 (15) 籃球場 ☆ \

104、n");　　printf("☆ (16) 生化樓 (17) 東門 (18) 文德樓 ☆ \n");　　printf("☆ (19) 排球場 (20) 第一教學(xué)樓 (21) 學(xué)生活動中心 ☆ \n");</

105、p>　　printf("☆ (22) 足球場 (23) 北門 (24) 西苑 ☆ \n");　　printf("☆ (25) 學(xué)生洗滌中心 (26) 開水房 (27) 自助服務(wù)點 ☆ \n");<p&

106、gt;　　printf("☆ ☆ ☆ ☆ ☆ ☆ ☆ ☆ ☆ ☆ ☆ ☆ ☆ ☆ ☆ ☆ ☆ ☆ ☆ ☆ ☆ ☆ ☆ \n\n");　　printf("請選擇導(dǎo)航功能：\n");　　printf("≈≈≈≈≈≈≈≈≈≈≈≈≈≈≈≈≈≈≈≈\n");

107、printf("≈ (1) 兩點最短距離導(dǎo)航 ≈\n");　　printf("≈ (2) 某點到其他所有點的最短距離 ≈\n");　　printf("≈ (3) 退出導(dǎo)航系統(tǒng) ≈\n");<p&

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

溫馨提示

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

算法課程設(shè)計--校園導(dǎo)航系統(tǒng)

文檔簡介

溫馨提示

最新文檔

評論

算法課程設(shè)計--校園導(dǎo)航系統(tǒng)

文檔簡介

溫馨提示

最新文檔

評論

免費下載