1、實(shí)驗(yàn)課程名稱 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì) 專 業(yè) 班 級(jí) 學(xué) 生 姓 名 學(xué) 號(hào) 指 導(dǎo) 教 師 2012至 2013學(xué)年第 一 學(xué)期第 1 至 9 周目錄一、概述：21.1 問(wèn)題描述21.2 系統(tǒng)實(shí)現(xiàn)的目標(biāo)21.3 系統(tǒng)實(shí)現(xiàn)方案2二、系統(tǒng)分析：32.1設(shè)計(jì)思想32.2設(shè)計(jì)要求32.3需求分析32.4 算法描述4三、概要設(shè)計(jì)：63.1 程序流程圖7四、詳細(xì)設(shè)計(jì)：84.1建立圖的存儲(chǔ)結(jié)構(gòu)84.2單源最短路徑84.3任意一對(duì)頂點(diǎn)間最短路徑94.4 建立有向圖的存儲(chǔ)結(jié)構(gòu)104.5迪杰斯特拉算法104.6弗洛伊德算法114.7 運(yùn)行主控程序12五、運(yùn)行與測(cè)試：13六、：總結(jié)與心得15附錄：程序代碼15一、概述：

2、1.1 問(wèn)題描述在交通網(wǎng)絡(luò)非常發(fā)達(dá),交通工具和交通方式不斷更新的今天,人們?cè)诔霾?、旅游或做其他出行時(shí)，不僅關(guān)心節(jié)省交通費(fèi)用，而且對(duì)里程和所需要的時(shí)間等問(wèn)題也感興趣。對(duì)于這樣一個(gè)人們關(guān)心的問(wèn)題，可用一個(gè)圖結(jié)構(gòu)來(lái)表示交通網(wǎng)絡(luò)系統(tǒng)，利用計(jì)算機(jī)建立一個(gè)交通咨詢系統(tǒng)。圖中的頂點(diǎn)表示城市，邊表示城市之間的交通關(guān)系。這個(gè)交通系統(tǒng)可以回答出行旅客提出的各種路徑選擇問(wèn)題。例如，問(wèn)題之一：“一位旅客要從A城到B城，他希望選擇一條途中中轉(zhuǎn)次數(shù)最少的路線。”假設(shè)圖中每一站都需要換車，那么這個(gè)問(wèn)題反映到圖上就是要找一條從頂點(diǎn)A到頂點(diǎn)B的所含邊數(shù)目最少的路徑。我們只需要從頂點(diǎn)A出發(fā)對(duì)圖作廣度優(yōu)先搜索，一旦遇到頂點(diǎn)B就終止

3、。由此所得廣度優(yōu)先生成樹上，從根頂點(diǎn)A到頂點(diǎn)B的路徑就是中轉(zhuǎn)次數(shù)最少的路徑。路徑上A與B之間的頂點(diǎn)就是路徑的中轉(zhuǎn)站，但這只是一類最簡(jiǎn)單的圖的最短路徑問(wèn)題。系統(tǒng)還可以回答諸如此類的等等的路徑選擇問(wèn)題。1.2 系統(tǒng)實(shí)現(xiàn)的目標(biāo)通過(guò)進(jìn)行課程設(shè)計(jì)，了解并初步掌握設(shè)計(jì)、實(shí)現(xiàn)較大系統(tǒng)的完整過(guò)程，包括：系統(tǒng)分析、編碼設(shè)計(jì)、系統(tǒng)集成、以及調(diào)試分析，熟練掌握數(shù)據(jù)結(jié)構(gòu)的選擇、設(shè)計(jì)、實(shí)現(xiàn)以及操作方法，為進(jìn)一步的應(yīng)用開(kāi)發(fā)打好基礎(chǔ)。 應(yīng)用所學(xué)數(shù)據(jù)結(jié)構(gòu)知識(shí)，獨(dú)立完成問(wèn)題分析，結(jié)合數(shù)據(jù)結(jié)構(gòu)理論知識(shí)，編寫程序求解指定問(wèn)題。 1.3 系統(tǒng)實(shí)現(xiàn)方案首先確定系統(tǒng)要實(shí)現(xiàn)怎樣的目的，實(shí)現(xiàn)這些目的需要先實(shí)現(xiàn)哪些程序，這就是核心部分，劃分出

4、模塊并寫出其源代碼，此程序大致分了六大模塊，由一個(gè)主函數(shù)組和五個(gè)自定義函數(shù)組成，而后是上機(jī)調(diào)試，將幾大模塊組成一個(gè)協(xié)調(diào)完整的能實(shí)現(xiàn)其功能的程序，最后提交設(shè)計(jì)報(bào)告二、系統(tǒng)分析：2.1設(shè)計(jì)思想用鄰接矩陣來(lái)存儲(chǔ)交通網(wǎng)絡(luò)圖的信息，運(yùn)用迪杰斯特拉算法實(shí)現(xiàn)圖上單源最短路徑問(wèn)題，然后運(yùn)用費(fèi)洛伊德算法實(shí)現(xiàn)圖中任意一對(duì)頂點(diǎn)間最短路徑問(wèn)題，這樣就會(huì)實(shí)現(xiàn)旅客所要咨詢的問(wèn)題。2.2設(shè)計(jì)要求該交通咨詢系統(tǒng)要完成城市網(wǎng)絡(luò)圖的存儲(chǔ)，并要實(shí)現(xiàn)求任意一個(gè)城市頂點(diǎn)到其他城市頂點(diǎn)的最短路徑問(wèn)題，還要實(shí)現(xiàn)任意兩個(gè)城市頂點(diǎn)間的 最短路徑問(wèn)題。故設(shè)計(jì)要分成三部分，一是建立交通網(wǎng)絡(luò)圖的存儲(chǔ)結(jié)構(gòu)；二是解決單源路徑問(wèn)題；最后再實(shí)現(xiàn)兩個(gè)城市之間

5、的最短路徑問(wèn)題。設(shè)計(jì)要求： 1.建立交通網(wǎng)絡(luò)網(wǎng)的存儲(chǔ)結(jié)構(gòu)。 2.總體設(shè)計(jì)要畫流程圖。 3.提供程序測(cè)試方案。 4.界面友好。2.3需求分析 根據(jù)要求，需要在系統(tǒng)中建立無(wú)向圖。系統(tǒng)應(yīng)該有高度靈活性，可以由用戶根據(jù)當(dāng)前交通網(wǎng)絡(luò)圖輸入初始數(shù)據(jù)，并且可以更改。系統(tǒng)根據(jù)用戶的輸入建立無(wú)向圖的結(jié)構(gòu)，并通過(guò)狄克斯特拉算法和弗洛伊德算法實(shí)現(xiàn)要求，并提供兩種功能供用戶選擇。2.4 算法描述錄入城市及道路數(shù)據(jù)查詢一個(gè)城市到其它城市的最短路徑根據(jù)無(wú)向圖建立查詢功能構(gòu)建交通網(wǎng)交通查詢系統(tǒng)預(yù)置城市間的距離查詢?nèi)我鈨沙鞘虚g的最短路徑狄克斯特拉算法的具體流程圖開(kāi) 始初始化距離和路徑i=1j=1;j+;jn弗洛伊德算法的具體

6、流程圖開(kāi) 始初始化距離和路徑設(shè)為從到的只以集合中的節(jié)點(diǎn)為中間節(jié)點(diǎn)的最短路徑的長(zhǎng)度輸出結(jié)果最短路徑經(jīng)過(guò)點(diǎn)k最短路徑不經(jīng)過(guò)點(diǎn)k三、概要設(shè)計(jì)：程序中將涉及下列兩個(gè)抽象數(shù)據(jù)類型：一個(gè)是圖，一個(gè)是隊(duì)列。 1、設(shè)定“圖”的抽象數(shù)據(jù)類型定義： ADT Graph 數(shù)據(jù)對(duì)象 V：V 是具有相同特性的數(shù)據(jù)元素的集合,稱為頂點(diǎn)集。 數(shù)據(jù)關(guān)系 R： R=VRVR = | v, w VP(v, w), 表示從v到w的弧， 謂詞P(v, w)定義了弧 的意義或信息基本操作 P：CreateGraph(&G,V,VR); 初始條件：V 是圖的頂點(diǎn)集，VR 是圖中弧的集合。 操作結(jié)果：按 V 和 VR 的定義構(gòu)造圖。 Lo

7、cateVex(G,u); 初始條件：圖 G 存在，u 和 G 中的頂點(diǎn)有相同特征。 操作結(jié)果：若 G 中存在頂點(diǎn) u，則返回該頂點(diǎn)在圖中位置；否則返回其他信息。 First_next_adj（G，v） ； 初始條件：圖 G 存在，v 是 G 中某個(gè)頂點(diǎn)。 操作結(jié)果：返回 V 的第一個(gè)鄰接頂點(diǎn)。若頂點(diǎn)在 G 中沒(méi)有鄰接頂點(diǎn)，則返回“空” 。 DFSTraverse(G,i); 初始條件：圖 G 存在，i 為某個(gè)頂點(diǎn)在鄰接矩陣中的位置。 操作結(jié)果：以 i 為起始點(diǎn)，對(duì)圖進(jìn)行深度優(yōu)先遍歷。 BFSTraverse(G,i); 初始條件：圖 G 存在，i 為某個(gè)頂點(diǎn)在鄰接矩陣中的位置。 操作結(jié)果：以

8、 i 為起始點(diǎn)，對(duì)圖進(jìn)行廣度優(yōu)先遍歷。 ADT Graph 2、設(shè)定隊(duì)列的抽象數(shù)據(jù)類型定義： ADT Queue 數(shù)據(jù)對(duì)象：D= a i a i BiTree, i N+ 數(shù)據(jù)關(guān)系：R1=| a i 1 , a i D ,i=2,，n 約定 a1 端為隊(duì)列頭， a n 端為隊(duì)列尾?；静僮鳎?InitQueue(&Q) 操作結(jié)果：構(gòu)造一個(gè)空隊(duì)列 Q。EnQueue(&Q,&e) 初始條件：隊(duì)列 Q 已存在。 操作結(jié)果：插入元素 e 為 Q 的新的隊(duì)尾元素。 DeQueue(&Q) 初始條件：隊(duì)列 Q 已存在。 操作結(jié)果：刪除 Q 的對(duì)頭元素，并返回其值。 QueueEmpty(&Q) 初始條件

9、：隊(duì)列 Q 已存在。操作結(jié)果：若 Q 為空隊(duì)列，則返回 1，否則 0。 QueueLenghth(Q) 初始條件：隊(duì)列 Q 已存在。 操作結(jié)果：返回 Q 的元素個(gè)數(shù)，即隊(duì)列長(zhǎng)度。 GetHead（Q，&e） 初始條件：Q 為非空隊(duì)列。 操作結(jié)果：用 e 返回 Q 的對(duì)頭元素。 ADT Queue 3、本程序包含三個(gè)模塊1）主程序模塊 void main( ) 選擇欲建圖的類型； 構(gòu)建圖并對(duì)其用鄰接矩陣的形式打?。?對(duì)圖進(jìn)行深度和廣度優(yōu)先搜索以及求某個(gè)頂點(diǎn)的第一鄰接點(diǎn)； 求某一源點(diǎn)到其余頂點(diǎn)的最短路徑。 2）圖模塊實(shí)現(xiàn)圖的抽象數(shù)據(jù)類型和基本操作 3）隊(duì)列模塊實(shí)現(xiàn)隊(duì)列的抽象數(shù)據(jù)類型及今本操作3.1

10、 程序流程圖四、詳細(xì)設(shè)計(jì)：4.1建立圖的存儲(chǔ)結(jié)構(gòu)首先定義交通圖的存儲(chǔ)結(jié)構(gòu)。鄰接矩陣是表示圖形中頂點(diǎn)之間相鄰關(guān)系的矩陣。設(shè)G=（V，E）是具有n個(gè)頂點(diǎn)的圖，則G的鄰接矩陣是具有如下定義的n階方陣。Ai，j= 當(dāng)鄰接矩陣的行表頭、列表頭順序一定時(shí)，一個(gè)圖的鄰接矩陣表示是唯一的。圖的鄰接矩陣表示，除了需用一個(gè)二維數(shù)組存儲(chǔ)頂點(diǎn)之間的相鄰關(guān)系的鄰接矩陣外，通常還需要使用一個(gè)具有n個(gè)元素的一維數(shù)組來(lái)存儲(chǔ)頂點(diǎn)信息，其中下標(biāo)為i的元素存儲(chǔ)頂點(diǎn)i的信息。因此，圖的鄰接矩陣的存儲(chǔ)結(jié)構(gòu)定義如下：#definf MVNum 88 /最大頂點(diǎn)數(shù)typedef struct VertexType vexsMVNum; /

11、頂點(diǎn)數(shù)組，類型假定為char型 Adjmatrix arcsMVNumMVNum; /鄰接矩陣，假定為int型MGraph;4.2單源最短路徑最短路徑的提法很多。在這里先討論單源最短路徑問(wèn)題：即已知有向圖（帶權(quán)），我們希望找出從某個(gè)源點(diǎn)SV到G中其余各頂點(diǎn)的最短路徑。為了敘述方便，我們把路徑上的開(kāi)始點(diǎn)稱為源點(diǎn)，路徑的最后一個(gè)頂點(diǎn)為終點(diǎn)。那么，如何求得給定有向圖的單源最短路徑呢？迪杰斯特拉（Dijkstra）提出按路徑長(zhǎng)度遞增產(chǎn)生諸點(diǎn)的最短路徑算法，稱之為迪杰斯特拉算法。迪杰斯特拉算法求最短路徑的實(shí)現(xiàn)思想是：設(shè)G=（V，E）是一個(gè)有向圖，結(jié)點(diǎn)集為，cost是表示G的鄰接矩陣，costij表示有向

12、邊的權(quán)。若不存在有向邊，則costij的權(quán)為無(wú)窮大（這里取值為32767）。設(shè)S是一個(gè)集合，其中的每個(gè)元素表示一個(gè)頂點(diǎn)，從源點(diǎn)到這些頂點(diǎn)的最短距離已經(jīng)求出。設(shè)頂點(diǎn)v1為源點(diǎn)，集合S的初態(tài)只包含一個(gè)元素，即頂點(diǎn)v1。數(shù)組dist記錄從源點(diǎn)到其他頂點(diǎn)當(dāng)前的最短距離，其初值為disti=costv1i,i=1,2,n。從S之外的頂點(diǎn)集合V-S中選出一個(gè)頂點(diǎn)w，使distw的值最小。于是從源點(diǎn)到達(dá)w只通過(guò)S中頂點(diǎn)，把w加入集合S中，調(diào)整dist中記錄的從源點(diǎn)到V-S中每個(gè)頂點(diǎn)v的距離：從原來(lái)的distv和distw+costwv中選擇較小的值作為新的distv。重復(fù)上述過(guò)程，直到V-S為空。最終結(jié)果是

13、：S記錄了從源點(diǎn)到該頂點(diǎn)存在最短路徑的頂點(diǎn)集合，數(shù)組dist記錄了源點(diǎn)到V中其余各頂點(diǎn)之間的最短路徑，path是最短路徑的路徑數(shù)組，其中pathi表示從源點(diǎn)到頂點(diǎn)i之間的最短路徑的前驅(qū)頂點(diǎn)。因此，迪杰斯特拉算法可用自然語(yǔ)言描述如下：初始化S和D，置空最短路徑終點(diǎn)集，置初始的最短路徑值；Sv1=TRUE; Dv1=0； /S集初始時(shí)只有源點(diǎn)，源點(diǎn)到源點(diǎn)的距離為0；While (S集中頂點(diǎn)數(shù)n)開(kāi)始循環(huán)，每次求得v1到某個(gè)v頂點(diǎn)的最短路徑，并加v到S集中；Sv=TRUE；更新當(dāng)前最短路徑及距離；4.3任意一對(duì)頂點(diǎn)間最短路徑任意一對(duì)頂點(diǎn)間最短路徑問(wèn)題，是對(duì)于給定的有向網(wǎng)絡(luò)圖G=（V，E），要對(duì)G中任

14、意一對(duì)頂點(diǎn)有序?qū)Α皏,w(vw)”,找出v到w的最短路徑。要解決這個(gè)問(wèn)題，我們可以依次把有向網(wǎng)絡(luò)圖中每個(gè)頂點(diǎn)作為源點(diǎn)，重復(fù)執(zhí)行前面討論的迪杰斯特拉算法n次，即可以求得每對(duì)頂點(diǎn)之間的最短路徑。這里還可以用另外一種方法，稱作費(fèi)洛伊德（Floyd）算法。費(fèi)洛伊德（Floyd）算法算法的基本思想是：假設(shè)求從頂點(diǎn) vi到vj的最短路徑。如果從vi到vj存在一條長(zhǎng)度為arcsij的路徑，該路徑不一定是最短路徑，還需要進(jìn)行n次試探。首先考慮路徑和是否存在。如果存在，則比較和的路徑長(zhǎng)度，取長(zhǎng)度較短者為當(dāng)前所求得的最短路徑。該路徑是中間頂點(diǎn)序號(hào)不大于1的最短路徑。其次，考慮從vi到vj是否包含有頂點(diǎn)v2為中間頂

15、點(diǎn)的路徑，若沒(méi)有，則說(shuō)明從vi到vj的當(dāng)前最短路徑就是前一步求出的；若有，那么可分解為和,而這兩條路徑是前一次找到的中間頂點(diǎn)序號(hào)不大于1的最短路徑，將這兩條路徑長(zhǎng)度相加就得到路徑的長(zhǎng)度。將該長(zhǎng)度與前一次中求出的從vi到vj的中間頂點(diǎn)序號(hào)不大于1的最短路徑比較，取其長(zhǎng)度較短者作為當(dāng)前求得的從vi到vj的中間頂點(diǎn)序號(hào)不大于2的最短路徑。依此類推，直到頂點(diǎn)vn加入當(dāng)前從vi到vj的最短路徑后，選出從vi到vj的中間頂點(diǎn)序號(hào)不大于n的最短路徑為止。由于圖G中頂點(diǎn)序號(hào)不大于n，所以vi到vj的中間頂點(diǎn)序號(hào)不大于n的最短路徑，已考慮了所有頂點(diǎn)作為中間頂點(diǎn)的可能性，因此，它就是vi到vj的最短路徑。4.4

16、建立有向圖的存儲(chǔ)結(jié)構(gòu)void CreateMGraph(MGraph * G,int n,int e) int i,j,k,w; for(i=1;ivexsi=(char)i; for(i=1;i=n;i+) for(j=1;jarcsij=Maxint; printf(輸入%d條邊的i,j及w:n,e); for(k=1;karcsij=w; printf(有向圖建立完畢n);4.5迪杰斯特拉算法void Dijkstra(MGraph *G,int v1,int n)int D2MVNum,P2MVNum;int v,i,w,min;enum boolean SMVNum;for(v=1;

17、varcsv1v; if(D2vMaxint) P2v=v1; else P2v=0; D2v1=0;Sv1=TRUE;for(i=2;in;i+) min=Maxint; for(w=1;w=n;w+) if(!Sw&D2wmin) v=w;min=D2w; Sv=TRUE; for(w=1;warcsvwarcsvw; P2w=v; printf(路徑長(zhǎng)度 路徑n); for(i=1;i=n;i+) printf(%5d,D2i); printf(%5d,i);v=P2i; while(v!=0) printf(-%d,v); v=P2v; printf(n); 4.6弗洛伊德算法void

18、 Floyd(MGraph *G,int n) int i,j,k,v,w; for(i=1;i=n;i+) for(j=1;jarcsij!=Maxint) Pij=j; else Pij=0; Dij=G-arcsij; for(k=1;k=n;k+) for(i=1;i=n;i+) for(j=1;j=n;j+) if(Dik+DkjDij) Dij=Dik+Dkj; Pij=Pik; 4.7 運(yùn)行主控程序void main()MGraph *G; int m,n,e,v,w,k; int xz=1; G=(MGraph *)malloc(sizeof(MGraph); printf(輸

19、入圖中頂點(diǎn)個(gè)數(shù)和邊數(shù)n,e:); scanf(%d,%d,&n,&e); CreateMGraph(G,n,e); while (xz!=0) printf(*求城市間的最短路徑*n); printf(1.求一個(gè)城市到所有城市的最短路徑n); printf(“2.求任意的兩個(gè)城市之間的最短路徑n); printf( 請(qǐng)選擇：1 或 2,選擇 0 退出:); scanf(%d,&xz); if(xz=2) Floyd(G,n); printf(輸入起點(diǎn)和終點(diǎn):v,w:); scanf(%d,%d,&v,&w); k=Pvw; if(k=0) printf(頂點(diǎn) %d 到 %d 無(wú)路徑!n,v,w

20、); else printf(從頂點(diǎn)%d到%d的最短路徑是:%d,v,w,v); while(k!=w) printf(%d,k); k=Pkw; printf(%d,w); printf(路徑長(zhǎng)度:%dn,Dvw); else if(xz=1) printf(求單源路徑，輸入源點(diǎn) v :); scanf(%d,&v); Dijkstra(G,v,n); printf(結(jié)束求最短路徑);五、運(yùn)行與測(cè)試：1、進(jìn)入查詢系統(tǒng)并設(shè)置城市個(gè)數(shù)及城市間連接情況2、進(jìn)入查詢界面，按要求“1”進(jìn)行查詢3、在查詢界面，按要求“2”進(jìn)行查詢4、退出查詢界面六、：總結(jié)與心得在第一次編譯時(shí)出現(xiàn)了很多錯(cuò)誤，是因?yàn)槲覍?duì)C

21、語(yǔ)言的不熟練，比如調(diào)用費(fèi)洛伊德算法時(shí)出現(xiàn)了調(diào)用的錯(cuò)誤，找了好久，才改正過(guò)來(lái)，還有就是for語(yǔ)句的運(yùn)用，由于本次程序要用很多for循環(huán)，我把一次for循環(huán)放到了上面for循環(huán)中，導(dǎo)致程序不能正確輸出結(jié)果。最后把調(diào)到外面才能運(yùn)行。通過(guò)本實(shí)驗(yàn)基本掌握了這兩個(gè)算法的應(yīng)用，編程過(guò)程中有過(guò)很多失誤，可知對(duì)平時(shí)的學(xué)習(xí)還有很多不夠仔細(xì)的地方，通過(guò)這次設(shè)計(jì)，我學(xué)到了很多。 附錄：程序代碼#include#include#define Num 288 /定義常量Num#define Maxint 31111enum booleanFALSE,TRUE; /定義布爾類型typedef char VertexType

22、;typedef int Adjmatrix;typedef struct VertexType vexsNum; /頂點(diǎn)數(shù)組， 類型假定為char型 Adjmatrix arcsNumNum;MGraph; / 鄰接矩陣， 假定為int型int D1Num,P1Num;int DNumNum,PNumNum;void CreateMGraph(MGraph *G,int n,int e); /采用鄰接矩陣表示法構(gòu)造有向圖G,n,e表示圖的當(dāng)前頂點(diǎn)數(shù)和邊數(shù)void Dijkstra(MGraph *G,int v1,int n); /狄克斯特拉算法的聲明void Floyd(MGraph *G

23、,int n); /弗洛伊德算法的聲明void main() MGraph *G; system(color 1f); /定義無(wú)向圖G int n,e,v,w,k; int m=1; G=(MGraph *)malloc(sizeof(MGraph); printf(*n); printf(* 歡迎使用交通查詢系統(tǒng) *n); printf(*=*n); printf(* PS:輸入完文本后，均以Enter結(jié)束!*n); printf(*輸入頂點(diǎn)和邊數(shù)時(shí)請(qǐng)使用“,”號(hào)隔 *n); printf(*開(kāi)! *n); printf(*n); printf(n); printf(使用查詢功能前，請(qǐng)輸入頂

24、點(diǎn)個(gè)數(shù)和邊數(shù)n,e：); scanf(%d,%d,&n,&e); CreateMGraph(G,n,e); /調(diào)用CreateMGraph有向圖函數(shù) while(m!=0) printf(=n); printf( _ 求城市之間的最短路徑 _ n); printf(=n); printf(1 : 求一個(gè)城市到其他所有城市的最短路徑n); printf(2 : 求任意的兩個(gè)城市之間的最短路徑n); printf(=n); printf( 請(qǐng)選擇：1 或 2 ，選擇 0 退出：n); scanf(%d,&m); if(m=2) Floyd(G,n); printf(請(qǐng)輸入起點(diǎn)和終點(diǎn)，用“,”號(hào)隔開(kāi)

25、：n); scanf(%d,%d,&v,&w); k=Pvw; if(k=0) printf(n輸出的結(jié)果：n頂點(diǎn)%d到%d無(wú)路徑!n,v,w); else printf(n輸出的結(jié)果：n從頂點(diǎn)%d到%d的最短路徑是: %d,v,w,v); while(k!=w) printf(%d,k); k=Pkw; printf(%d,w); printf(n 路徑長(zhǎng)度: %dn,Dvw); else if(m=1) printf(請(qǐng)輸入起點(diǎn)編號(hào)：n); scanf(%d,&v); Dijkstra(G,v,n); printf(程序已結(jié)束!謝謝您的使用!n);void CreateMGraph(MGraph *G,int n,int e) /構(gòu)建城市的無(wú)向圖 int i,j,k,w; for(i=1;ivexsi=(char)i; for(i=1;i=n;i+) for(j=1;jarcsij=Maxint; /距離初始化 if(i=j) G-arcsij=0; printf(n請(qǐng)輸入