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

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

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

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

文檔簡介

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

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

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

4、;　　2方案設(shè)計(jì)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)運(yùn)行流程圖4　　3.2 迪杰斯特拉算法流程圖5　　4 功能模塊代碼實(shí)現(xiàn)6

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

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

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

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

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

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

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

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

14、明湖 (6) 圖書館 　　(7) 分析測試中心 (8) 第二教學(xué)樓 (9) 羽毛球場 　　(10) 勵(lì)志樓 (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ù)點(diǎn)　　2.2.2 導(dǎo)航圖建立模塊　　根據(jù)課程設(shè)計(jì)功能要求設(shè)計(jì)人性化的導(dǎo)航界面，方便用戶根據(jù)自己實(shí)際需要查詢的信息選擇相應(yīng)的

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

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

19、主函數(shù)模塊是整個(gè)程序的入口，包括對各變量、數(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ù)，實(shí)現(xiàn)導(dǎo)航系統(tǒng)的功能。　　3 流程圖　　3.1 系統(tǒng)運(yùn)行流程

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

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

22、.arcs[1][0] =20;　　作用：使0號節(jié)點(diǎn)到1號節(jié)點(diǎn)的路徑賦值為20，應(yīng)為是無向圖，所以1號節(jié)點(diǎn)到0號節(jié)點(diǎn)的路徑長度也應(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ù)描述：輸出各個(gè)節(jié)點(diǎn)的編號，及本系統(tǒng)所提供的查詢方式，方便導(dǎo)航。　　具體導(dǎo)航菜單設(shè)計(jì)如下：　　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) 勵(lì)志樓 (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ù)點(diǎn) ☆ \n");　　printf("☆ ☆ ☆ ☆ ☆ ☆ ☆ ☆ ☆ ☆ ☆ ☆ ☆ ☆ ☆ ☆ ☆ ☆ ☆ ☆ ☆ ☆ ☆ \n\n");　　printf

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

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定點(diǎn)到其余定點(diǎn)V的最短路徑P[v]及其帶權(quán)長度D[v][5]。若P[v][w]為True，則w是從V0

42、到V當(dāng)前求得最短路徑上的頂點(diǎn)。Final[v]為True當(dāng)且僅當(dāng)V∈S，即已經(jīng)求得從V0到V的最短路徑。　　利用迪杰斯特拉算法設(shè)計(jì)最短路徑算法如下：　　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個(gè)頂點(diǎn)　　min=INFINITY;&

47、lt;p>　　for(w=0;w<G.vexnum;++w)　　if(!final[w])　　if(d[w]<min) //如有W點(diǎn)離更近　　{　　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 運(yùn)行調(diào)試　　查詢系統(tǒng)導(dǎo)航界面　　圖5.1 查詢系統(tǒng)導(dǎo)航截圖　　兩點(diǎn)最短距離導(dǎo)航　　圖5.

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

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

54、，機(jī)械工業(yè)出版社， 1999　　[4］《數(shù)據(jù)結(jié)構(gòu)與算法分析》，CLIFFORD A. SHAFFER著，張銘、劉曉丹譯，電子工業(yè)出版社，1998　　[5] 《計(jì)算機(jī)算法設(shè)計(jì)與分析》，王曉東，電子工業(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、 //最大頂點(diǎn)個(gè)數(shù)　　#define INFINITY 32767 //最大值　　typedef struct　　{　　char* vexs[MAX_V]; //頂點(diǎn)向量<

57、p>　　int arcs[MAX_V][MAX_V];//鄰接矩陣　　int vexnum,arcnum;//圖的當(dāng)前頂點(diǎn)數(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("分別輸入起點(diǎn)

64、和終點(diǎn)代號以空格分開\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ā)點(diǎn)：");　　scanf("%d",&v0);　　ShortPath(G,v0,P,D);</p&g

69、t;　　printf("%s到其他所有點(diǎn)的最短路徑為：\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("選擇錯(cuò)誤，請重新輸入！\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] = "勵(lì)志樓"; 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ù)點(diǎn)";　　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個(gè)頂點(diǎn)　　min=INFINITY;　　for(w=0;w<G.v

97、exnum;++w)　　if(!final[w])　　if(d[w]<min) //如有W點(diǎn)離更近　　{　　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) 勵(lì)志樓 (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ù)點(diǎn) ☆ \n");<p&

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

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

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

溫馨提示

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)方式做保護(hù)處理，對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯，并不能對任何下載內(nèi)容負(fù)責(zé)。
6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容，請與我們聯(lián)系，我們立即糾正。
7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

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

文檔簡介

溫馨提示

最新文檔

評論

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

文檔簡介

溫馨提示

最新文檔

評論

免費(fèi)下載