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

1、<p><b>　　摘要</b></p><p>　　本次課程設(shè)計(jì)主要核心為利用迪杰斯特拉算法實(shí)現(xiàn)無(wú)向圖的最短路徑的計(jì)算和求解。要求理解迪杰斯特拉算法的具體實(shí)現(xiàn)流程、學(xué)會(huì)正確使用該算法求解實(shí)際問(wèn)題。本次課程設(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)的最短路徑。</p><p>　　本程序要求

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

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

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

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

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

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

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

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

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

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

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

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

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

15、14) 凌云樓 (15) 籃球場(chǎng) </p><p>　　(16) 生化樓 (17) 東門(mén) (18) 文德樓 </p><p>　　(19) 排球場(chǎng) (20) 第一教學(xué)樓 (21) 學(xué)生活動(dòng)中心 </p><p>　　(22) 足球場(chǎng)

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

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

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

19、主函數(shù)模塊是整個(gè)程序的入口，包括對(duì)各變量、數(shù)據(jù)結(jié)構(gòu)以及要使用的函數(shù)的聲明等。</p><p>　　主函數(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)的功能。</p><p><b>　　3 流程圖</b></p><p>　　3.1 系統(tǒng)運(yùn)行流程

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

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

22、.arcs[1][0] =20;</p><p>　　作用：使0號(hào)節(jié)點(diǎn)到1號(hào)節(jié)點(diǎn)的路徑賦值為20，應(yīng)為是無(wú)向圖，所以1號(hào)節(jié)點(diǎn)到0號(hào)節(jié)點(diǎn)的路徑長(zhǎng)度也應(yīng)賦值為20。</p><p><b>　　具體賦值如下：</b></p><p>　　G.arcs[0][1] = G.arcs[1][0] =20;</p><p>　　

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

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

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

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

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

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

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

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

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

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

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

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

35、 (6) 圖書(shū)館 ☆ \n");</p><p>　　printf("☆ (7) 分析測(cè)試中心 (8) 第二教學(xué)樓 (9) 羽毛球場(chǎng) ☆ \n");</p><p>　　printf("☆ (10) 勵(lì)志樓 (11) 學(xué)生公寓中心 (12) 食堂區(qū)

36、 ☆ \n");</p><p>　　printf("☆ (13) 醫(yī)務(wù)室 (14) 凌云樓 (15) 籃球場(chǎng) ☆ \n");</p><p>　　printf("☆ (16) 生化樓 (17) 東門(mén) (18) 文德樓 ☆ \

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

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

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

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

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

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

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

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

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

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

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

48、<p><b>　　min=d[w];</b></p><p><b>　　}</b></p><p>　　final[v]=1;</p><p>　　have[k]=v;</p><p><b>　　k++;</b></p><p>　　f

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

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

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

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

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

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

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

56、 //最大頂點(diǎn)個(gè)數(shù)</p><p>　　#define INFINITY 32767 //最大值</p><p>　　typedef struct</p><p><b>　　{</b></p><p>　　char* vexs[MAX_V]; //頂點(diǎn)向量</p><

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

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

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

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

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

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

63、gt;<p><b>　　case 1:</b></p><p><b>　　{</b></p><p><b>　　while(1)</b></p><p><b>　　{</b></p><p>　　printf("分別輸入起點(diǎn)

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

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

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

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

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

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

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

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

72、b></p><p>　　printf("選擇錯(cuò)誤，請(qǐng)重新輸入！\n");</p><p><b>　　}</b></p><p>　　if(choice==3)</p><p><b>　　{</b></p><p>　　printf(&qu

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

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

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

76、uot;; G.vexs[4] = "靜明湖"; G.vexs[5] = "圖書(shū)館";</p><p>　　G.vexs[6] = "分析測(cè)試中心"; G.vexs[7] = "第二教學(xué)樓"; G.vexs[8] = "羽毛球場(chǎng)";</p><p>　　G.

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

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

79、= "學(xué)生活動(dòng)中心";</p><p>　　G.vexs[21] = "足球場(chǎng)"; G.vexs[22] = "北門(mén)"; G.vexs[23] = "西苑";</p><p>　　G.vexs[24] = "學(xué)生洗滌中心";G.vexs[25] = "開(kāi)水房

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

106、gt;　　printf("☆ ☆ ☆ ☆ ☆ ☆ ☆ ☆ ☆ ☆ ☆ ☆ ☆ ☆ ☆ ☆ ☆ ☆ ☆ ☆ ☆ ☆ ☆ \n\n");</p><p>　　printf("請(qǐng)選擇導(dǎo)航功能：\n");</p><p>　　printf("≈≈≈≈≈≈≈≈≈≈≈≈≈≈≈≈≈≈≈≈\n");</p><p>　　

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