北理珠校園導(dǎo)游咨詢與最短路徑

1、北京理工大學(xué)珠海學(xué)院 課程設(shè)計(jì)說明書 _2014_ _2015_ 學(xué)年第 _ 1 學(xué)期 題目：北理珠校園導(dǎo)游咨詢與最短路徑 學(xué)院：計(jì)算機(jī)學(xué)院 專業(yè)班級(jí)： 學(xué) 號(hào)： 學(xué)生姓名： 指導(dǎo)教師：王琳 成 績(jī)： 時(shí) 間： 2014年12月30日 2014 年 12 月 30 日 設(shè)計(jì)任務(wù)書 20142015學(xué)年第1學(xué)期 學(xué)生姓名：專業(yè)班級(jí)： 指導(dǎo)教師：王琳工作部門：計(jì)算機(jī)學(xué)院 一、課程設(shè)計(jì)題目 北理珠校園導(dǎo)游咨詢與最短路徑 二、課程設(shè)計(jì)內(nèi)容（含技術(shù)指標(biāo)） 【問題描述】 從北京理工大學(xué)珠海學(xué)院的平面圖中選取有代表性景點(diǎn)（10-15個(gè)），抽象 成一個(gè)無向帶權(quán)圖。以圖中頂點(diǎn)表示景點(diǎn)，邊上的權(quán)值表 示兩地之間距

2、離。 本程序的目的是為用戶提供路徑咨詢。 根據(jù)用戶指定的始點(diǎn)和終 點(diǎn)輸出相應(yīng)路徑，或者根據(jù)用戶指定的景點(diǎn)輸出景點(diǎn)的信息。 【任務(wù)要求】 從北京理工大學(xué)珠海學(xué)院的平面圖中選取有代表性景點(diǎn)（10-15 個(gè)），抽象成一個(gè)無向帶權(quán)圖。以圖中頂點(diǎn)表示校內(nèi)各景點(diǎn)，存放景 點(diǎn)名稱、代號(hào)、簡(jiǎn)介等信息；以邊表示路徑，存放路徑長(zhǎng)度等信息。 為來訪客人提供圖中任意景點(diǎn)相關(guān)信息的查詢。 為來訪客人提供圖中任意景點(diǎn)的問路查詢，即查詢?nèi)我鈨蓚€(gè)景點(diǎn) 之間的一條最短的簡(jiǎn)單路徑。 區(qū)分汽車線路與步行線路。 【測(cè)試數(shù)據(jù)】 北理珠校園導(dǎo)游圖（距離可估計(jì)）。 三、進(jìn)度安排 1.初步設(shè)計(jì)：寫出初步設(shè)計(jì)思路，進(jìn)行修改完善，并進(jìn)行初步 設(shè)

3、計(jì)。 2 .詳細(xì)設(shè)計(jì)：根據(jù)確定的設(shè)計(jì)思想，進(jìn)一步完善初步設(shè)計(jì)內(nèi)容， 按要求編寫出數(shù)據(jù)結(jié)構(gòu)類型定義、各算法程序、主函數(shù)。編譯分析調(diào) 試錯(cuò)誤。 3 .測(cè)試分析：設(shè)計(jì)幾組數(shù)據(jù)進(jìn)行測(cè)試分析，查找存在的設(shè)計(jì)缺 陷，完善程序。 4 .報(bào)告撰寫：根據(jù)上面設(shè)計(jì)過程和結(jié)果，按照要求寫出設(shè)計(jì)報(bào) 告。 5 .答辯考核驗(yàn)收：教師按組（人）檢查驗(yàn)收，并提出相關(guān)問題， 以便檢驗(yàn)設(shè)計(jì)完成情況。 四、基本要求 1.在設(shè)計(jì)時(shí)，要嚴(yán)格按照題意要求獨(dú)立進(jìn)行設(shè)計(jì)，不能隨意更 改。若確因條件所限，必須要改變課題要求時(shí)，應(yīng)在征得指導(dǎo)教師同 意的前提下進(jìn)行。 2 .在設(shè)計(jì)完成后，應(yīng)當(dāng)場(chǎng)運(yùn)行和答辯，由指導(dǎo)教師驗(yàn)收，只有 在驗(yàn)收合格后才能算設(shè)

4、計(jì)部分的結(jié)束。 3 .設(shè)計(jì)結(jié)束后要寫出課程設(shè)計(jì)報(bào)告，以作為整個(gè)課程設(shè)計(jì)評(píng)分 的書面依據(jù)和存檔材料。設(shè)計(jì)報(bào)告以規(guī)定格式的電子文檔書寫、 打印 并裝訂，報(bào)告格式嚴(yán)格按照模板要求撰寫，排版及圖、表要清楚、工 整。 從總體來說，所設(shè)計(jì)的程序應(yīng)該全部符合要求，問題模型、求解 算法以及存儲(chǔ)結(jié)構(gòu)清晰；具有友好、清晰的界面；設(shè)計(jì)要包括所需要 的輔助程序，如必要的數(shù)據(jù)輸入、輸出、顯示和錯(cuò)誤檢測(cè)功能；操作 使用要簡(jiǎn)便；程序的整體結(jié)構(gòu)及局部結(jié)構(gòu)要合理；設(shè)計(jì)報(bào)告要符合規(guī) 范。 課程負(fù)責(zé)人簽名: 課程設(shè)計(jì)分工安排 姓名 課程設(shè)計(jì)負(fù)責(zé)工作 備注 成績(jī)?cè)u(píng)定表 姓名 成績(jī)?cè)u(píng)定權(quán)重 總分 總成績(jī) （五分制） 平時(shí)成績(jī) 20 報(bào)

5、告成績(jī) 50 答辯成績(jī) 30 通過數(shù)據(jù)結(jié)構(gòu)“圖”構(gòu)成抽象數(shù)據(jù)類型，該系統(tǒng)運(yùn)用了數(shù)組表示法（領(lǐng)結(jié)矩陣） 初始化圖，分別存儲(chǔ)數(shù)據(jù)元素（景點(diǎn)）和數(shù)據(jù)元素（路段）之間的關(guān)系，迪杰斯 特拉算法來描述各景點(diǎn)所有游覽路徑，佛洛依德算法設(shè)計(jì)景點(diǎn)之間的最短路徑， 結(jié)合上述算法設(shè)計(jì)了一個(gè)校園導(dǎo)航與最短路徑系統(tǒng)，供來訪北理珠的客人使用， 為其提供方便。 關(guān)鍵詞：概要設(shè)計(jì)詳細(xì)設(shè)計(jì)軟件測(cè)試 I 目錄 課程設(shè)計(jì)說明書1 設(shè)計(jì)任務(wù)書2 成績(jī)?cè)u(píng)定表6 摘要7 目錄8 1. 前言9 1.1問題的描述9 1.2算法輸入9 1.3算法輸出9 2. 概要設(shè)計(jì)11 2.1要點(diǎn)描述11 2.2模塊分解11 3. 詳細(xì)設(shè)計(jì)12 3.1算法

6、程序流程圖 12 3.2界面設(shè)計(jì)13 4. 軟件測(cè)試17 5. 參考文獻(xiàn)19 6. 心得體會(huì) 錯(cuò)誤!未定義書簽。 答辯記錄表28 1. 刖言 1.1問題的描述 從北京理工大學(xué)珠海學(xué)院的平面圖中選取有代表性景點(diǎn)（10-15個(gè)），抽象 成一個(gè)無向帶權(quán)圖。以圖中頂點(diǎn)表示景點(diǎn)，邊上的權(quán)值表示兩地之間距離。本程 序的目的是為用戶提供路徑咨詢。 根據(jù)用戶指定的始點(diǎn)和終點(diǎn)輸出相應(yīng)路徑， 或 者根據(jù)用戶指定的景點(diǎn)輸出景點(diǎn)的信息 1.2算法輸入 MGraphCreatGraph(void) MGraph G; / 初始化 in ti, j; G.vex num = :10; 14 個(gè)頂點(diǎn) G.arc num =

7、 16; 14 條弧 for (i = 0; ivG.vex num; i+) G.vexsi.num = i; /第i個(gè)景點(diǎn)的編號(hào)為i strcpy_s(G.vexsO.name,北理圖書館); 1.3算法輸出 voidcmd(void); 初始化圖 主界面 瀏覽全部景點(diǎn) 該點(diǎn)到其它全部路徑 MGraphCreatGraph(void);/ void Me nu( void);/ void Browser(MGraph *G);/ void ShortestPath_DIJ(MGraph * G);/ void Floyd(MGraph *G); / void Search(MGraph *

8、G); / void prin tMatrix(MGraph *G);/ 兩景點(diǎn)最短路徑 查看景點(diǎn)信息 輸出領(lǐng)結(jié)矩陣 2. 概要設(shè)計(jì) 2.1要點(diǎn)描述 用圖的算法進(jìn)行構(gòu)造，用鄰接表建立圖，圖的每一個(gè)頂點(diǎn)代表相應(yīng)的景點(diǎn)。 然后 再用深度優(yōu)先遍歷進(jìn)行搜索，查找所需的路徑。再用迪杰特斯拉算法求出一個(gè)景 點(diǎn)到其他景點(diǎn)之間的最佳路徑。然后再用弗洛伊德算法求出要查詢的出發(fā)點(diǎn)到目 的地的最短路徑。 2.2模塊分解 （1）主菜單（Menu：存放著所有的選擇供用戶查詢。用戶可通過輸入編號(hào)來 查詢自己想要獲得的信息 （2） 瀏覽校園全景（Browser）：采用深度遍歷圖進(jìn)行所有景點(diǎn)瀏覽，將遍歷景 點(diǎn)信息輸出。 （3

9、）查看各景點(diǎn)游覽路線（ShortestPath_DIJ）：用戶輸入一個(gè)景點(diǎn)，采用迪杰 斯特拉算法將從該景點(diǎn)起所有路徑查出并輸出在屏幕上。 （4） 選擇出發(fā)點(diǎn)和目的地（Floyd）:用戶輸入一個(gè)出發(fā)點(diǎn)和一個(gè)目的地編號(hào)，采 用弗洛伊德算法求出發(fā)點(diǎn)到目的地的最短路徑。 （5）查看景點(diǎn)信息（Search）:直接輸入編號(hào)進(jìn)行單個(gè)景點(diǎn)查詢。 （6）顯示圖的鄰接矩陣（print） （7）退出系統(tǒng)（exit） 3.1算法程序流程圖 3.詳細(xì)設(shè)計(jì) 3.2界面設(shè)計(jì) 主菜單(MenU : prin tf(n printf( prin tf(1. prin tf(2. prin tf(3. prin tf( 4. p

10、rin tf(5. prin tf(6. printf( prin tf( 選項(xiàng)-:); 北京理工大學(xué)珠海學(xué)院導(dǎo)游圖n); void Menu() /定義主菜單 n); 瀏覽校園全景n); 查看各景點(diǎn)所有游覽路線n); 選擇出發(fā)點(diǎn)和目的地n); 查看景點(diǎn)信息n); 顯示此圖的鄰接矩陣n); 退出系統(tǒng)n); n); 瀏覽校園全景(Browser): void Browser(MGraph *G) int v; printf(編號(hào)景點(diǎn)名稱簡(jiǎn)介n); for (v = 0; vvex num; v+) prin tf(| %-4d |%-16s | %-56s |n, G-vexsv. num, G

11、-vexsv. name, G-vexsv.i ntroducti on); 查看各景點(diǎn)游覽路線(ShortestPath_DIJ ): voidShortestPath_DIJ(MGraph * G) _ 保證輸入編號(hào)有 int v, w, i, min, t = 0, x, flag = 1, v0; flag=1 效 in t fin al20, D20, p2020; while (flag) printf(請(qǐng)輸入一個(gè)起始景點(diǎn)編號(hào):); scanf_s(%d, /輸入一個(gè)值賦給 vO if (v0G-vex num) printf(景點(diǎn)編號(hào)不存在！請(qǐng)重新輸入景點(diǎn)編號(hào)：); sea nf

12、_s(%d, if (vO = 0 for (v = 0; vvex num; v+) finalv = 0; v不屬于s，即v頂點(diǎn)還沒有走過 Dv = G-arcsv0v.adj; v0到 v 的弧權(quán)值 for (w = 0; wvex num; w+) pvw = 0;/設(shè)置空路徑 if (DvINFINITY) pvv0 = 1; pvv = 1; v0是從 v0 到 v 的頂點(diǎn)，v 是從 v0到v的頂點(diǎn) Dv0 = 0; finalv0 = 1; /初始化，v0到v0的帶權(quán)路徑長(zhǎng)度為 0, 最短路徑,v0頂點(diǎn)屬于s集 for (i = 1; ivexnum; i+) /其余 G.vex

13、num-1 個(gè)頂點(diǎn) min = INFINITY; /當(dāng)前所知離v0頂點(diǎn)的最近距離 for (w = 0; wvex num; w+) if (!finalw) w頂點(diǎn)在 v-s 中 if (Dwmin) v = w; min = Dw; w頂點(diǎn)離 v0 頂點(diǎn) 更近 finalv = 1;/離v0頂點(diǎn)最近的v加入s集 for (w = 0; wvex num; w+) /更新當(dāng)前的最短路徑及距離 if (!finalw for (x = 0; xvex num; x+) Pwx = pvx; pww = 1; /用來更新到每一個(gè)頂點(diǎn)的最短路徑 for (v = 0; vvex num; v+)

14、 if (v0 != v) pri ntf(%s, G-vexsv0. name); /輸出字符串 for (w = 0; wvex num; w+) if (pvw t+; if (tG-vexnum - 1 /ShortestPath_DIJ end 選擇出發(fā)點(diǎn)和目的地(Floyd): void Floyd(MGraph *G) int v, u, i, w, k, j, flag = 1, p101010, D1010; for (v = 0; vvex num; v+) /各對(duì)結(jié)點(diǎn)之間初始已知路徑及距離 for (w = 0; wvex num; w+) Dvw = G-arcsvw.

15、adj; for (u = 0; uvex num; u+) pvwu = 0; if (DvwINFINITY) pvwv = 1; pvww = 1; for (u = 0; uvex num; u+) for (v = 0; vvex num; v+) for (w = 0; wvex num; w+) if (Dvu + DuwDvw) /從 v 經(jīng) u 到 w 的一條路 徑更短 Dvw = Dvu + Duw; /修改權(quán)值 for (i = 0; ivex num; i+) pvwi = pvui | puwi; while (flag) printf(請(qǐng)輸入出發(fā)點(diǎn)和目的地的編號(hào):)

16、; scan f_s(%d%d, if (kG-vexnum | jG-vexnum) printf(景點(diǎn)編號(hào)不存在！請(qǐng)重新輸入出發(fā)點(diǎn)和目的地的編號(hào):); sca nf_s(%d%d, _ if (k = 0 printf(%s, G-); for (u = 0; uvex num; u+) if (pkju prin tf(-%s, G-vexsj. name); printf( 總路線長(zhǎng) %dmn, Dkj); /Floyd end 查看景點(diǎn)信息(Search): void Search(MGraph *G) int k, flag = 1; while (flag)

17、printf(請(qǐng)輸入要查詢的景點(diǎn)編號(hào):); scan f_s(%d, if (kG-vex num) printf(景點(diǎn)編號(hào)不存在！請(qǐng)重新輸入景點(diǎn)編號(hào):); sca nf_s(%d, _ if (k = 0 printf(| %-4d | %-16s | %-56s | n, G-vexsk.num, G-, G-vexsk.i ntroductio n); /Search end 顯示圖的鄰接矩陣(print): voidpri ntMatrix(MGraph *G) int v, w, t = 0; prin tf( 圖的鄰接矩陣為：n); for (v = 0; vv

18、ex num; v+) for (w = 0; wvex num; w+) if (G-arcsvw.adj = INFINITY) prin tf(g ); elsepri ntf(%-7d, G-arcsvw.adj); t+; if (t%G-vex num = 0) prin tf(n); WIN DOWSsy$tem32cmd.sxe 4.軟件測(cè)試 校園全景： 號(hào) 012345 T.可堂廳決型吐心廳 客圖坂翟麗飯飯中餐剋桂 總踐一工僧二三遞生泳癌 雖，忘軟T蘋昂kv洗叨 簡(jiǎn)介 圏書館是學(xué)枝的丈就恬駐中心，是為學(xué)校教學(xué)的學(xué)術(shù)性機(jī)購(gòu). 忖干田艷場(chǎng)對(duì)面檯供譜買就飯菜僅芳生選捧. I,.-H

19、：；.IL -tt:/. .1： Il.r-.r-tllj.TT 卷生程宅區(qū)中間地段，常書各式零金以匪用產(chǎn)品 位于學(xué)生住宅中恆地段.為附近的學(xué)生據(jù)供寒梏恂化肯誨擇 位丁學(xué)生住宅苯尾地段.坯境別具 格，理足 種述押 學(xué)檢成立的快堰服,1匚，猜足廣農(nóng)瞬q收發(fā)也表的s來 Z J快趣中右知為附近的學(xué)生提慶勞樣的優(yōu)託逸狂 忡干學(xué)枚后丄坡腔段，期有三個(gè)小池，于卻1年苗川瞬噸.， 生上課的地 揀教學(xué)樓-畜式技孚設(shè)備都齊全. 北U.舞I丈寧壇泄夕陲尋喲匡 1 輒覽桂園全呆 宜右各豈耳所有醫(yī)危瑙農(nóng) 耳誕彈出也dm的地 *.蟲甘號(hào)巳f言總 乳顯.川此圖的那播逋陣 取迥出至?xí)?- 頂. I1A- 選擇出發(fā)點(diǎn)和目的地

20、: m*e. SO- 0 *+1 0 22/路徑長(zhǎng)度 ArCell, AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM; / 一個(gè)二維數(shù)組，數(shù)組里元素類 型為整型 typedefstruct /圖中頂點(diǎn)表示主要景點(diǎn)，存放景點(diǎn)的編號(hào)、名稱、簡(jiǎn)介等信息， char n ame30; intnum; char introduction100; 簡(jiǎn)介 in fotype;/ 數(shù)據(jù)域 typedefstruct in fotypevexsMAX_VERTEX_NUM;/ 頂點(diǎn)的數(shù)據(jù)域 AdjMatrix arcs;/ 鄰接矩陣 intvexnum, arcnum;/圖的當(dāng)前頂點(diǎn)

21、數(shù)和弧數(shù) MGraph; MGraph b;/全局變量 voidcmd(void); MGraphCreatGraph(void);/ void Menu( void);/ void Browser(MGraph *G);/ voidShortestPath_DIJ(MGraph * G);/ void Floyd(MGraph *G);/ void Search(MGraph *G);/ voidpri ntMatrix(MGraph *G);/ void mai n( void)/ 定義主函數(shù) system(mode con: cols=100 lin es=40); cmd(); / 調(diào)

22、用 cmd () void cmd(void) / 定義 cmd () in ti; b = CreatGraph(); MGraph G; Me nu(); scan f_s(%d, while (i != 6) switch (i) case 1:system(cls); Browser( Menu(); break; case 2:system(cls); ShortestPath_DIJ( Menu(); break; case 3:system(cls); Floyd( Menu(); break; case 4:system(cls); Search( Men u(); break

23、; case 5:system(cls); printMatrix( Menu(); break; case 6:exit(1); break; default:break; scanf_s(%d, II 輸入的值 d 賦給 i MGraphCreatGraph(void) II 初始化 MGraph G; in ti, j; G.vexnum = 10;II14 個(gè)頂點(diǎn) G.arcnum = 16;II14 條弧 for (i = 0; iG.vex num; i+) G.vexsi.num = i; II第i個(gè)景點(diǎn)的編號(hào)為i strcpy_s(G.,北理圖書館 ”)；

24、IIstrcpy 的頭文件是 string.h strcpy_s(G.roduction,圖書館是學(xué)校的文獻(xiàn)信息中心，是為學(xué)校教學(xué)的學(xué)術(shù)性 機(jī)構(gòu)?！?； strcpy_s(G.,第一飯?zhí)?; strcpy_s(G.roduction, ”位于田 徑場(chǎng)對(duì) 面，提 供諸多 款飯 菜供 學(xué)生選 擇。 ); strcpy_s（G.,教工餐廳）; strcpy_s（G.vexs2.i ntroductio n, ”臨近明德樓的一個(gè)餐廳，為師生們提供最便捷的伙食 ”）； strcpy_s（G.,零食前線）; s

25、trcpy_s（G.roduction,位于學(xué)生住宅區(qū)中間地段，銷售各式零食以及日用產(chǎn)品 ）; strcpy_s（G.,第二飯?zhí)茫? strcpy_s（G.roduction,位于學(xué)生住宅中間地段，為附近的學(xué)生提供多樣的伙食 選擇 ）; strcpy_s（G.,第三飯?zhí)茫? strcpy_s（G.roduction,位于學(xué)生住宅末尾地段，環(huán)境別具一格，也是一種選擇 ）; strcpy_s（G.,快遞中心”）； strcpy_s（G.roduction,學(xué)校成立的快

26、遞服務(wù)中心，滿足廣大師生收發(fā)包裹的需 求 ”）； strcpy_s（G.,學(xué)生餐廳）; strcpy_s（G.vexs7.i ntroductio n, ”位于快遞中心旁，為附近的學(xué)生提供多樣的伙食選擇 ）; strcpy_s（G.,游泳池）; strcpy_s（G.roduction,位于學(xué)校后山坡路段，擁有三個(gè)水池，于2014年10月 建成。 ”）； strcpy_s（G.,明德樓）; strcpy_s（G.roduction,廣大學(xué)生上課的地點(diǎn)，分四棟教學(xué)樓，各式教學(xué)設(shè)備都 齊全。）； for

27、 （i = 0; iG.vex num; i+） for （j = 0; jG.vex nu m; j+） G.arcsij.adj = INFINITY; G.arcs01.adj = 420; G.arcs02.adj = 480; G.arcs12.adj = 80; G.arcs13.adj = 410; G.arcs14.adj = 220; G.arcs19.adj = 700; G.arcs23.adj = 50; G.arcs29.adj = 550; G.arcs35.adj = 190; G.arcs45.adj = 320; G.arcs56.adj = 100; G.a

28、rcs57.adj = 120; G.arcs58.adj = 210; G.arcs67.adj = 50; G.arcs78.adj = 120; G.arcs89.adj = 300; for (i = 0; iG.vex num; i+) for (j = 0; jG.vex nu m; j+) G.arcsji.adj = G.arcsij.adj; / 無向網(wǎng) return G; void Menu()/定義主菜單 printf(” n); printf( n); printf( n); printf( n); printf( n); printf( n); printf( n);

29、 printf( n); printf( n); printf(選項(xiàng)-:); 北京理工大學(xué)珠海學(xué)院導(dǎo)游圖 1.瀏覽校園全景 2.查看各景點(diǎn)所有游覽路線 3.選擇出發(fā)點(diǎn)和目的地 4.查看景點(diǎn)信息 5.顯示此圖的鄰接矩陣 6.退出系統(tǒng) void Browser(MGraph *G) in t v; printf( i11 1n); printf(丨編號(hào)丨景點(diǎn)名稱丨簡(jiǎn)介丨n); for (v = 0; vvex num; v+) printf( | %-4d | %-16s | %-56s | n,G-vexsv.num,G-, G-vexsv.i ntroduct ion);

30、printf( 111 1n); /迪杰斯特拉算法來計(jì)算出起點(diǎn)到各個(gè)頂點(diǎn)之間的最短路徑,v0為起點(diǎn) voidShortestPath_DIJ(MGraph * G) intv, w, i, min, t = 0, x, flag = 1, v0; /flag=1 保證輸入編號(hào)有效 int final20, D20, p2020; /用迪杰斯特拉算法求網(wǎng)G的v0頂點(diǎn)到其余頂點(diǎn)v的最短路徑Pv及帶權(quán)長(zhǎng)度Dv /若Pvw為1，則w是從v0到v當(dāng)前求得最短路徑上的頂點(diǎn) /finalv為1當(dāng)且僅當(dāng)v屬于s(s是已求得最短路徑的終點(diǎn)的集合)，即已經(jīng)求得從v0到 v的最短路徑 while (flag) pr

31、intf(請(qǐng)輸入一個(gè)起始景點(diǎn)編號(hào)：”)； scan f_s(%d, / 輸入一個(gè)值賦給 v0 if (v0G-vex num) printf(景點(diǎn)編號(hào)不存在！請(qǐng)重新輸入景點(diǎn)編號(hào)：”)； scan f_s(%d, if (v0 = 0 for (v = 0; vvex num; v+) finalv = 0; /v不屬于s,即v頂點(diǎn)還沒有走過 Dv = G-arcsvOv.adj;v0 到 v 的弧權(quán)值 for (w = 0; wvex num; w+) Pvw = 0;/設(shè)置空路徑 if (DvINFINITY) pvvO = 1; pvv = 1;/v0是從v0到v的頂點(diǎn)，v是從v0到v的頂

32、點(diǎn) Dv0 = 0; finalv0 = 1;/初始化，v0到v0的帶權(quán)路徑長(zhǎng)度為0，最短路徑,v0頂點(diǎn)屬 于s集 /開始主循環(huán)，每次求得v0到某個(gè)v頂點(diǎn)的最短路徑，并加v到s集 for (i = 1; ivexnum; i+)/ 其余 G.vexnum-1 個(gè)頂點(diǎn) min = INFINITY; /當(dāng)前所知離v0頂點(diǎn)的最近距離 for (w = 0; wvex num; w+) if (!finalw)/w 頂點(diǎn)在 v-s 中 if (Dwmin) v = w; min = Dw; /w 頂點(diǎn)離 v0 頂點(diǎn)更近 finalv = 1;/離v0頂點(diǎn)最近的 v加入s集 for (w = 0; w

33、vexnum; w+)/更新當(dāng)前的最短路徑及距離 if (!finalw for (x = 0; xvex num; x+) Pwx = pvx; pww = 1; /用來更新到每一個(gè)頂點(diǎn)的最短路徑 for (v = 0; vvex num; v+) if (v0 != v) pri ntf(%s, G-vexsv0. name); / 輸出字符串 for (w = 0; wvex num; w+) if (pvw t+; if (tG-vexnum - 1 /ShortestPath_DIJ end void Floyd(MGraph *G) /用Floyd算法求圖中各對(duì)頂點(diǎn)v和w之間的最短路徑Pvw及其 /帶權(quán)長(zhǎng)度Dvw。若Pvwu為1,則u是從v到w當(dāng)前求得最短 /路徑上的頂點(diǎn)。 int v, u, i, w, k, j, flag = 1, p101010, D1010; for (v = 0; vvex num; v+)/各對(duì)結(jié)點(diǎn)之間初始已知路徑及距離 for (w = 0; wvex num; w+) Dvw = G-arcsvw.adj; for (u = 0; uvex num; u+