數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告Dijkstra算法求最短路徑

1、中南大學(xué)數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì) 題 目 第9題 Dijkstra算法求最短路徑 學(xué)生姓名 XXXX 指導(dǎo)教師 XXXX 學(xué) 院 信息科學(xué)與工程學(xué)院 專業(yè)班級(jí) XXXXXXX 完成時(shí)間 XXXXXXX 目錄第1章 問(wèn)題分析與任務(wù)定義-3 1.1 課程設(shè)計(jì)題目-3 1.2 原始數(shù)據(jù)的輸入格式-3 1.3 實(shí)現(xiàn)功能-3 1.4 測(cè)試用例-3 1.5 問(wèn)題分析-3第2章 數(shù)據(jù)結(jié)構(gòu)的選擇和概要設(shè)計(jì)-4 2.1 數(shù)據(jù)結(jié)構(gòu)的選擇-4 2.2 概要設(shè)計(jì)-4第3章 詳細(xì)設(shè)計(jì)與編碼-6 3.1 框架的建立-6 3.2 點(diǎn)結(jié)構(gòu)體的定義-7 3.3 創(chuàng)立帶權(quán)值有向圖-8 3.4 鄰接矩陣的顯示-9 3.5 遞歸函數(shù)的應(yīng)用-

2、10 3.6 Dijkstra算法實(shí)現(xiàn)最短路徑-10第4章 上機(jī)調(diào)試-11 4.1 記錄調(diào)試過(guò)程中錯(cuò)誤和問(wèn)題的處理-11 4.2 算法的時(shí)間課空間性能分析-11 4.3 算法的設(shè)計(jì)、調(diào)試經(jīng)驗(yàn)和體會(huì)-11第5章 測(cè)試結(jié)果-12第6章 學(xué)習(xí)心得體會(huì)-12第7章 參考文獻(xiàn)-12附錄-12第1章 問(wèn)題分析與任務(wù)定義1、 課程設(shè)計(jì)題目：1.1題目：采用適當(dāng)?shù)拇鎯?chǔ)結(jié)構(gòu)實(shí)現(xiàn)帶權(quán)有向圖的存儲(chǔ)，建立，輸入、顯示，以及使用Dijkstra算法，尋找和輸出帶權(quán)有向圖中某個(gè)源點(diǎn)到其余各點(diǎn)的最短路徑1.2要求：采用適當(dāng)?shù)拇鎯?chǔ)結(jié)構(gòu)實(shí)現(xiàn)帶權(quán)有向圖的存儲(chǔ)，建立，輸入、顯示，以及使用Dijkstra算法。1.3具體任務(wù)：建立圖

3、的存儲(chǔ)模塊，建立圖的輸出模塊，在建圖后從單源點(diǎn)開(kāi)始求最短路徑，并顯示出來(lái)。2. 原始數(shù)據(jù)的輸入格式2.1建圖：2.1.1數(shù)字2.2顯示：2.2.1數(shù)字+逗號(hào)+數(shù)字+回車 2.2.2字母+回車3. 實(shí)現(xiàn)功能3.1建立有向圖3.2顯示存儲(chǔ)的有向圖3.3顯示從頂點(diǎn)到其他各個(gè)頂點(diǎn)的最短路徑和是否存在路徑4. 測(cè)試用例4.1正確數(shù)據(jù)：輸入頂點(diǎn)；邊值信息輸出結(jié)果：最短路徑是否存在，存在的情況最短路徑是多少，其次是不存在。5. 問(wèn)題分析實(shí)現(xiàn)本程序要解決以下幾個(gè)問(wèn)題：5.1如何存儲(chǔ)一個(gè)有向圖。5.2如何在界面中輸出該有向圖。5.3如何定義起始源點(diǎn)。5.4如何選擇出最短路徑。5.5找到的最短路徑如何輸出。第2章

4、 數(shù)據(jù)結(jié)構(gòu)的選擇和概要設(shè)計(jì)1.數(shù)據(jù)結(jié)構(gòu)的選擇： 在圖的結(jié)構(gòu)中，任意兩個(gè)頂點(diǎn)之間都可能存在關(guān)系，比線性表和樹(shù)要復(fù)雜。由于不存在嚴(yán)格的前后順序，因而不能采用簡(jiǎn)單的數(shù)組來(lái)存儲(chǔ)圖;另一方面，如果采用鏈表，由于圖中各頂點(diǎn)的度數(shù)不盡相同，最小度數(shù)和最大度數(shù)可能相差很大，如果按最大度數(shù)的頂點(diǎn)來(lái)設(shè)計(jì)鏈表的指針域，則會(huì)浪費(fèi)很多存儲(chǔ)單元，反之，如果按照各個(gè)頂點(diǎn)設(shè)計(jì)不同的鏈表結(jié)點(diǎn)，則會(huì)給操作帶來(lái)很大的困難。 在此我選用鄰接矩陣的存儲(chǔ)結(jié)構(gòu)。采用鄰接矩陣存儲(chǔ)，很容易判斷圖中兩個(gè)頂點(diǎn)是否相連，也容易求出各個(gè)頂點(diǎn)的度。不過(guò)任何事情都不是完美的，采用鄰接矩陣存儲(chǔ)圖時(shí)，測(cè)試其邊的數(shù)目，必須檢查邊二維數(shù)組的所有元素，時(shí)間復(fù)雜度為

5、O（n2）,這對(duì)于頂點(diǎn)很多而邊較少的圖（稀疏圖）是非常不合算的。以鄰接矩陣存儲(chǔ)有向圖。2.概要設(shè)計(jì)2.1對(duì)于最短路徑問(wèn)題：最短路徑是在實(shí)際應(yīng)用中非常有用的工具，我們常見(jiàn)的兩種最短路徑是：（1）從某源點(diǎn)到其余各頂點(diǎn)之間的最短路徑。（2）每一段頂點(diǎn)之間的最短路徑在這里我們解決第一類問(wèn)題。2.2 Dijkstra算法用于求最短路徑：Dijkstra算法是按路徑長(zhǎng)度遞增的次序逐步產(chǎn)生源點(diǎn)到其他頂點(diǎn)間的最短路徑。算法建立一個(gè)頂點(diǎn)集合S，初始時(shí)該集合只有源點(diǎn)V0，然后逐步將已求得最短路徑的頂點(diǎn)加入到集合中，直到全部頂點(diǎn)都在集合S中，算法結(jié)束。 2.3 Dijkstra算法思想設(shè)costi,j=0，S為已經(jīng)

6、求得最短路徑的頂點(diǎn)集合，distancei數(shù)組的每個(gè)元素表示當(dāng)前狀態(tài)下源點(diǎn)V0到Vi的最短路徑。算法如下：1) 初始化：S=V0, distancei=cost0,i。2) 選擇一個(gè)終點(diǎn)Vj，滿足distancej=MIN distancei|ViV-S。3）把Vj加入到S中。4）修改distance數(shù)組元素，修改邏輯為對(duì)于所有不在S中的頂點(diǎn)Vi.if(distancej+costi,j< distancei) distancei= distancej +costi,j 5) 重復(fù)操作2）、3）、4），直到全部頂點(diǎn)加入到S中。輸入頂點(diǎn)名稱輸入每條邊的信息返回每個(gè)結(jié)點(diǎn) 的位置創(chuàng)建圖Dijk

7、stra算法的實(shí)現(xiàn)Dw<n輸出源點(diǎn)與其他點(diǎn)最短距離開(kāi)始輸入頂點(diǎn)邊個(gè)數(shù)結(jié)束2.4 實(shí)現(xiàn)流程在任意圖中實(shí)現(xiàn)求最短路徑問(wèn)題，第一步是要能成功的在內(nèi)存中輸入圖的信息，圖的信息有兩個(gè)，一是頂點(diǎn)個(gè)數(shù)，二是每?jī)牲c(diǎn)之間的權(quán)值信息。當(dāng)建立圖之后，對(duì)圖進(jìn)行遍歷才能使用Dijkstra算法求出最短路徑；在完成了圖的建立之后，用Dijkstra算法的思想，從單源點(diǎn)開(kāi)始，求出到各個(gè)頂點(diǎn)的最短路徑，并能夠?qū)崿F(xiàn)顯示功能。 程序流程圖：(1) 輸入頂點(diǎn)個(gè)數(shù)n，邊的條數(shù)，初始化鄰接矩陣。(2)初始化所每條邊的權(quán)值與Dh中(3) 找出v0到圖中其他各點(diǎn)的最小值 經(jīng)過(guò)改最小值的點(diǎn)到除它外其他各點(diǎn)的最小值 直到s中的所有值全部

8、被處理過(guò)， (4) 輸出各最短路徑的長(zhǎng)度Dw算法的思想，從單源點(diǎn)開(kāi)始，求出到各個(gè)頂點(diǎn)的最短路徑，并能夠?qū)崿F(xiàn)顯示功能。第3章 詳細(xì)設(shè)計(jì)和編碼3.1框架的建立typedef char VertexType;/定義圖的頂點(diǎn)為字符型 typedef int VRType; /頂點(diǎn)關(guān)系類型typedef int InfoType;/該弧相關(guān)信息 typedef struct ArcCellVRType adj;/權(quán)值 InfoType *info;/弧相關(guān)信息的指針ArcCell;typedef structVertexType vexsMAX_VERTEX_NUM;/一維數(shù)組，存儲(chǔ)頂點(diǎn)ArcCell

9、arcsMAX_VERTEX_NUMMAX_VERTEX_NUM;/鄰接矩陣 ：二維數(shù)組，存儲(chǔ)邊和弧int vexnum,arcnum;/圖的當(dāng)前頂點(diǎn)數(shù)和弧數(shù) MGrph;/鄰接矩陣表示的圖3.1.1頂點(diǎn)的定義typedef char VertexType;/定義圖的頂點(diǎn)為字符型 頂點(diǎn)的最大個(gè)數(shù)253.1.2ArcCell arcsMAX_VERTEX_NUMMAX_VERTEX_NUM;二維數(shù)組用于存放鄰接矩陣，每個(gè)位置代表的值為圖中的權(quán)值，其余用無(wú)窮大3000表示。3.2點(diǎn)結(jié)構(gòu)體的定義/* 確定位置函數(shù) */int LocateVex(MGrph *G,VertexType v) int

10、j,b; for(b=0;b<G->vexnum;b+)/在所有頂點(diǎn)中尋找 if(G->vexsb=v)/找到所找的頂點(diǎn)在b位置 j=b; break; /ifreturn(j); /LocateVex3.3創(chuàng)立帶權(quán)值有向圖首先輸入該有向圖的頂點(diǎn)數(shù)n,然后依次輸入各個(gè)頂點(diǎn)及邊長(zhǎng)（輸入的頂點(diǎn)的序號(hào)應(yīng)該小于頂點(diǎn)的數(shù)目）。/* 有向圖的建立 */void Creat_YG(MGrph *G)int i,k,j,n; VertexType v1,v2; int w=1;printf("請(qǐng)輸入頂點(diǎn)個(gè)數(shù)和弧數(shù) 如括號(hào)里的方式（3,3）:");/讀入頂點(diǎn)個(gè)數(shù)和弧的個(gè)數(shù)s

11、canf("%d,%d",&G->vexnum,&G->arcnum);/讀出邊和弧的信息 printf("n"); /換行輸出 for(i=0;i<G->vexnum;i+) printf("請(qǐng)輸入圖的第%d個(gè)頂點(diǎn):",w);/輸入指定的頂點(diǎn) w+; fflush(stdin); scanf("%c",&G->vexsi); printf("n"); for(i=0;i<G->vexnum;i+) for(j=0;j<G-

12、>vexnum;j+) G->arcsij.adj=INFINITY; G->=NULL; for(k=0;k<G->arcnum;k+)/輸入各弧并構(gòu)造鄰接矩陣 printf("請(qǐng)輸入邊的起點(diǎn)和終點(diǎn)和權(quán)值如（v1,v2,n）:");/起始點(diǎn)和終點(diǎn)和兩點(diǎn)之間對(duì)應(yīng)的權(quán)值 fflush(stdin); scanf("%c,%c,%d",&v1,&v2,&n); printf("n"); i=LocateVex(G,v1);/確定v1的位置 j=LocateVex(

13、G,v2);/確定v2的位置 G->arcsij.adj=n;/邊<v1,v2>的權(quán)值賦為1，如需要權(quán)值操作則相應(yīng)修改一下即可 G->=NULL;/如需要有相關(guān)信息則相對(duì)應(yīng)輸入，在這里我設(shè)置為空 /第二個(gè)forgetchar(); /Creat_YGvoid juzhen(MGrph *G)/用矩陣來(lái)存儲(chǔ)并顯示出結(jié)果 int i,j,k; printf("鄰接矩陣顯示：n"); printf("t"); for(i=0;i<G->vexnum;i+) printf("t%5c"

14、,G->vexsi); for(j=0;j<G->vexnum;j+) printf("nn"); printf("t%5c",G->vexsj); for(k=0;k<G->vexnum;k+) if(G->arcsjk.adj<INFINITY) printf("t%5d",G->arcsjk.adj); else printf("t 3000"); /無(wú)權(quán)值的直接輸出最大值 3.4鄰接矩陣的顯示在圖的鄰接矩陣顯示中，分別利用for循環(huán)輸出了矩陣的行列標(biāo)，使

15、矩陣很明了。void juzhen(MGrph *G)/用矩陣來(lái)存儲(chǔ)并顯示出結(jié)果 int i,j,k; printf("鄰接矩陣顯示：n"); printf("t"); for(i=0;i<G->vexnum;i+) printf("t%5c",G->vexsi); for(j=0;j<G->vexnum;j+) printf("nn"); printf("t%5c",G->vexsj); for(k=0;k<G->vexnum;k+) if(G-

16、>arcsjk.adj<INFINITY) printf("t%5d",G->arcsjk.adj); else printf("t 3000"); /無(wú)權(quán)值的直接輸出最大值 3.5遞歸函數(shù)應(yīng)用3.5.1思想是patn數(shù)組來(lái)表示前驅(qū)頂點(diǎn)的位置，然后遞歸輸出每個(gè)頂點(diǎn)的前驅(qū)void Short(MGrph *G,int path,int i,int w) /遞歸函數(shù)是用來(lái)輸出從源點(diǎn)出發(fā)到終點(diǎn)之前的頂點(diǎn) /思想是patn數(shù)組來(lái)表示前驅(qū)頂點(diǎn)的位置，然后遞歸輸出每個(gè)頂點(diǎn)的前驅(qū) int k; k=pathi; if(k!=w) Short(G,pa

17、th,k,w ); printf("%c,",G->vexsk);/輸出k位置的頂點(diǎn)值 3.6 Dijkstra 算法實(shí)現(xiàn)最短路徑設(shè)圖以鄰接矩陣cost存儲(chǔ)，矩陣中各元素的值為各邊的權(quán)值。頂點(diǎn)間無(wú)邊時(shí)其對(duì)應(yīng)權(quán)值用無(wú)窮大表示。從頂點(diǎn)V0到其它各頂點(diǎn)間的最短路徑的具體步驟如下：a) 變量定義：定義整型數(shù)組S,這是一個(gè)頂點(diǎn)集合，初始時(shí)該集合只有源點(diǎn)v0，然后逐步將以求得最短路徑的頂點(diǎn)加入到該集合中，直到全部頂點(diǎn)都在集合S中，算法結(jié)束。定義兩個(gè)整型變量dis、mindis均用來(lái)標(biāo)志圖中最短的那一條路徑。b) 初始化：初始化dist數(shù)組的值即為cost數(shù)組中存放的權(quán)值。 dis

18、ti=costv0i 初始化求到每個(gè)頂點(diǎn)的最短路徑時(shí)都經(jīng)過(guò)v0頂點(diǎn)。pathi.pnode0=v0初始化記錄經(jīng)過(guò)的頂點(diǎn)數(shù)都為0。 pathi.num=0; 初始化頂點(diǎn)集合s為空，即還未開(kāi)始。si=0; c) 源點(diǎn)的選擇:將v0頂點(diǎn)加入到頂點(diǎn)集合s中。 sv0=1d) 利用for循環(huán)選擇一個(gè)終點(diǎn)Vj,使其滿足V0到Vj距離最短，同時(shí)將Vj加入集合S中。e) 根據(jù)j頂點(diǎn)調(diào)整當(dāng)前的最短路徑，若滿足disti> distj+costji,則修改disti的值。同時(shí)V0到Vi的最短路徑中經(jīng)過(guò)的頂點(diǎn)數(shù)加1，即pathi.num+; 并將經(jīng)過(guò)的頂點(diǎn)存入數(shù)組pnode即pathi.pnodepathi.

19、num=j f) 此時(shí)一趟求最短路徑完畢，將終點(diǎn)V1添加到路徑中。g) 循環(huán)執(zhí)行d),e),f)操作，直到全部頂點(diǎn)加入到S中。第4章 上機(jī)調(diào)試4.1記錄調(diào)試過(guò)程中錯(cuò)誤和問(wèn)題的處理 1) 當(dāng)輸入格式不符合程序要求時(shí)，會(huì)出現(xiàn)循環(huán)2) 當(dāng)兩頂點(diǎn)間沒(méi)有路徑時(shí)，權(quán)值為無(wú)窮大，但在本程序中只能用一個(gè)具體的數(shù)字2000代替抽象的無(wú)窮大。3) 在程序的調(diào)試過(guò)程可暫時(shí)多加一些輸出語(yǔ)句以便及時(shí)查看一下中間運(yùn)行情況，并對(duì)程序規(guī)格說(shuō)明作調(diào)整和改動(dòng)。4.2算法的時(shí)間和空間性能分析4.2.1時(shí)間復(fù)雜度對(duì)于n個(gè)頂點(diǎn)的有向圖，求一個(gè)頂點(diǎn)到其他頂點(diǎn)的最短路徑的時(shí)間為O(n)，調(diào)整最短路徑的循環(huán)共執(zhí)行n-1次，是二層循環(huán)，所以，

20、時(shí)間復(fù)雜度是O（n2）。4.2.2空間復(fù)雜度 采用鄰接矩陣存儲(chǔ)有向圖，應(yīng)處理每?jī)蓚€(gè)頂點(diǎn)之間的關(guān)系，所以空間復(fù)雜度為O（n2）。4.3算法設(shè)計(jì)、調(diào)試的經(jīng)驗(yàn)和體會(huì) Dijkstra算法在上課的時(shí)候曾作為重點(diǎn)講過(guò)，所以在做查找最短路徑的算法時(shí)很流暢，但是在輸出最短路徑的時(shí)候遇到了很大的阻力。因?yàn)樵诙x結(jié)點(diǎn)時(shí)，使用的是結(jié)構(gòu)體數(shù)組，所以當(dāng)處理V0到每個(gè)結(jié)點(diǎn)的最短路徑時(shí)，導(dǎo)致無(wú)法具體記錄經(jīng)過(guò)的頂點(diǎn)數(shù)，只能記錄源點(diǎn)、終點(diǎn)前一頂點(diǎn)以及終點(diǎn)。所以本程序在輸出最短路徑時(shí)有較大的瑕疵，還需進(jìn)一步修改。第5章 測(cè)試結(jié)果5.1測(cè)試結(jié)果：注意問(wèn)題：1、輸入頂點(diǎn)個(gè)數(shù)：最大不超過(guò)25，請(qǐng)輸入羅馬數(shù)字，若輸入其他符號(hào)，無(wú)意義；

21、2、以“字母 字母 數(shù)字”的格式輸入圖的信息，輸入第一個(gè)字母為原點(diǎn)，第二個(gè)字母為終點(diǎn)，輸入“數(shù)字”為權(quán)值，最后輸入一個(gè)“字母”為頂點(diǎn)輸入。輸入完成； 3、在輸入完成后，屏幕顯示鄰接矩陣與最短路徑。第6章 學(xué)習(xí)心得體會(huì) 通過(guò)對(duì)本次課程設(shè)計(jì)的學(xué)習(xí)與交流，使我學(xué)習(xí)到一部分很重要的關(guān)于編程方面思想，同時(shí)也獲得了部分學(xué)習(xí)其他學(xué)科的方法。學(xué)習(xí)重在于體會(huì)，體會(huì)這種學(xué)科給我?guī)?lái)的思考，給我?guī)?lái)由淺入深的演算心得。做一次課程設(shè)計(jì)，不僅僅是為了完成某項(xiàng)任務(wù)，而在于是否能從這次任務(wù)中總結(jié)出一些處理同類任務(wù)的方法和技巧。每次全力的付出，都會(huì)有或多或少的收獲。通過(guò)對(duì)本次課程設(shè)計(jì)涉及的問(wèn)題的分析和處理，了解到學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)

22、對(duì)編程的技巧和思想方法。以前也了解過(guò)數(shù)據(jù)結(jié)構(gòu)相關(guān)的書籍，但沒(méi)有深入的學(xué)習(xí)，本次上機(jī)課程設(shè)計(jì)從選題上也把學(xué)習(xí)的方法應(yīng)用其中，在編程時(shí)算法的理解和分析十分重要，首先的弄懂它的基本框架，用什么來(lái)算法來(lái)實(shí)現(xiàn)，最后通過(guò)查找部分資料，修改調(diào)試，總結(jié)心得，就是一種進(jìn)步。第7章 參考文獻(xiàn)6.1：嚴(yán)蔚敏 吳偉明 編著的數(shù)據(jù)結(jié)構(gòu)（C語(yǔ)言版）6.2：楊曉波 主編 王 弘 王聰華 胡 永 副主編的數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)指導(dǎo)（C語(yǔ)言版）附件：#include<stdio.h>#include<stdlib.h>#define MAX_VERTEX_NUM 25 /最大頂點(diǎn)個(gè)數(shù)#define INFINIT

23、Y 3000/最大值typedef char VertexType;/定義圖的頂點(diǎn)為字符型 typedef int VRType; /頂點(diǎn)關(guān)系類型typedef int InfoType;/該弧相關(guān)信息 typedef struct ArcCellVRType adj;/權(quán)值 InfoType *info;/弧相關(guān)信息的指針ArcCell;typedef structVertexType vexsMAX_VERTEX_NUM;/一維數(shù)組，存儲(chǔ)頂點(diǎn)ArcCell arcsMAX_VERTEX_NUMMAX_VERTEX_NUM;/鄰接矩陣 ：二維數(shù)組，存儲(chǔ)邊和弧int vexnum,arcnum

24、;/圖的當(dāng)前頂點(diǎn)數(shù)和弧數(shù) MGrph;/鄰接矩陣表示的圖/* 確定位置函數(shù) */int LocateVex(MGrph *G,VertexType v) int j,b; for(b=0;b<G->vexnum;b+)/在所有頂點(diǎn)中尋找 if(G->vexsb=v)/找到所找的頂點(diǎn)在b位置 j=b; break; /ifreturn(j); /LocateVex/* 有向圖的建立 */void Creat_YG(MGrph *G)int i,k,j,n; VertexType v1,v2; int w=1;printf("請(qǐng)輸入頂點(diǎn)個(gè)數(shù)和弧數(shù) 如括號(hào)里的方式（3,3

25、）:");/讀入頂點(diǎn)個(gè)數(shù)和弧的個(gè)數(shù)scanf("%d,%d",&G->vexnum,&G->arcnum);/讀出邊和弧的信息 printf("n"); /換行輸出 for(i=0;i<G->vexnum;i+) printf("請(qǐng)輸入圖的第%d個(gè)頂點(diǎn):",w);/輸入指定的頂點(diǎn) w+; fflush(stdin); scanf("%c",&G->vexsi); printf("n"); for(i=0;i<G->vex

26、num;i+) for(j=0;j<G->vexnum;j+) G->arcsij.adj=INFINITY; G->=NULL; for(k=0;k<G->arcnum;k+)/輸入各弧并構(gòu)造鄰接矩陣 printf("請(qǐng)輸入邊的起點(diǎn)和終點(diǎn)和權(quán)值如（v1,v2,n）:");/起始點(diǎn)和終點(diǎn)和兩點(diǎn)之間對(duì)應(yīng)的權(quán)值 fflush(stdin); scanf("%c,%c,%d",&v1,&v2,&n); printf("n"); i=LocateVex(G,v1

27、);/確定v1的位置 j=LocateVex(G,v2);/確定v2的位置 G->arcsij.adj=n;/邊<v1,v2>的權(quán)值賦為1，如需要權(quán)值操作則相應(yīng)修改一下即可 G->=NULL;/如需要有相關(guān)信息則相對(duì)應(yīng)輸入，在這里我設(shè)置為空 /第二個(gè)forgetchar(); /Creat_YGvoid juzhen(MGrph *G)/用矩陣來(lái)存儲(chǔ)并顯示出結(jié)果 int i,j,k; printf("鄰接矩陣顯示：n"); printf("t"); for(i=0;i<G->vexnum;i+)

28、printf("t%5c",G->vexsi); for(j=0;j<G->vexnum;j+) printf("nn"); printf("t%5c",G->vexsj); for(k=0;k<G->vexnum;k+) if(G->arcsjk.adj<INFINITY) printf("t%5d",G->arcsjk.adj); else printf("t 3000"); /無(wú)權(quán)值的直接輸出最大值 void Short(MGrph *

29、G,int path,int i,int w) /遞歸函數(shù)是用來(lái)輸出從源點(diǎn)出發(fā)到終點(diǎn)之前的頂點(diǎn) /思想是patn數(shù)組來(lái)表示前驅(qū)頂點(diǎn)的位置，然后遞歸輸出每個(gè)頂點(diǎn)的前驅(qū) int k; k=pathi; if(k!=w) Short(G,path,k,w ); printf("%c,",G->vexsk);/輸出k位置的頂點(diǎn)值 void ShortestPath(MGrph *G,int w) /Dijkstrs算法應(yīng)用int i,k,m,n,min; int final30,path30,D30;/定義三個(gè)數(shù)組，final標(biāo)記該頂點(diǎn)是否在最短路徑上 /path用來(lái)記錄頂點(diǎn)的前驅(qū)頂點(diǎn)的位置，D是用來(lái)記錄從源點(diǎn)到該點(diǎn)的最短路徑長(zhǎng)度 for(i=0;i<G->vexnum;i+) pathi=w;/首先把所有頂點(diǎn)的前驅(qū)頂點(diǎn)