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

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

已閱讀1頁，還剩16頁未讀，繼續(xù)免費閱讀

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

文檔簡介

1、　　《數(shù)據(jù)結(jié)構(gòu)》課程設(shè)計　　題目第9題 Dijkstra算法求最短路徑 　　學生姓名 XXXX 　　指導教師

2、 XXXX 　　學院信息科學與工程學院 　　專業(yè)班級 XXXXXXX 　　完成時間 XXXXXXX

3、 　　目錄　　問題分析與任務(wù)定義---------------------------------------------------------------------3　　1.1 課程設(shè)計題目------------------

4、-----------------------------------------------------------3　　1.2 原始數(shù)據(jù)的輸入格式--------------------------------------------------------------------3　　1.3 實現(xiàn)功能------------------------

5、-----------------------------------------------------------3　　1.4 測試用例-----------------------------------------------------------------------------------3　　1.5 問題分析--------------

6、---------------------------------------------------------------------3　　數(shù)據(jù)結(jié)構(gòu)的選擇和概要設(shè)計------------------------------------------------------------4　　2.1 數(shù)據(jù)結(jié)構(gòu)的選擇--------------------

7、------------------------------------------------------4　　2.2 概要設(shè)計-----------------------------------------------------------------------------------4　　詳細設(shè)計與編碼--------------------

8、---------------------------------------------------------6　　3.1 框架的建立---------------------------------------------------------------------------------6　　3.2 點結(jié)構(gòu)體的定義--------------

9、-------------------------------------------------------------7　　3.3 創(chuàng)立帶權(quán)值有向圖------------------------------------------------------------------------8　　3.4 鄰接矩陣的顯示----------------

10、-----------------------------------------------------------9　　3.5 遞歸函數(shù)的應(yīng)用---------------------------------------------------------------------------10　　3.6 Dijkstra算法實現(xiàn)最短路徑------

11、--------------------------------------------------------10　　上機調(diào)試------------------------------------------------------------------------------------11　　4.1 記錄調(diào)試過程中錯誤和問題的處理-------

12、--------------------------------------------11　　4.2 算法的時間課空間性能分析------------------------------------------------------------11　　4.3 算法的設(shè)計、調(diào)試經(jīng)驗和體會---------------------------------

13、------------------------11　　測試結(jié)果-----------------------------------------------------------------------------------12　　學習心得體會-----------------------------------------------------

14、------------------------12　　參考文獻-----------------------------------------------------------------------------------12　　附錄---------------------------------------------------------

15、---------------------------------------------12　　問題分析與任務(wù)定義　　課程設(shè)計題目：　　1.1題目：采用適當?shù)拇鎯Y(jié)構(gòu)實現(xiàn)帶權(quán)有向圖的存儲，建立，輸入、顯示，以及使用Dijkstra算法，

16、尋找和輸出帶權(quán)有向圖中某個源點到其余各點的最短路徑　　1.2要求：采用適當?shù)拇鎯Y(jié)構(gòu)實現(xiàn)帶權(quán)有向圖的存儲，建立，輸入、顯示，以及使用Dijkstra算法。　　1.3具體任務(wù)：建立圖的存儲模塊，建立圖的輸出模塊，在建圖后從單源點開始求最短路徑，并顯示出來。　　原始數(shù)據(jù)的輸入格式

17、　　2.1建圖：2.1.1數(shù)字　　2.2顯示：2.2.1數(shù)字+逗號+數(shù)字+回車　　2.2.2字母+回車　　實現(xiàn)功能　　3.1建立有向圖

18、　　3.2顯示存儲的有向圖　　3.3顯示從頂點到其他各個頂點的最短路徑和是否存在路徑　　測試用例　　4.1正確數(shù)據(jù)：輸入頂點；邊值信息　　輸出結(jié)果：最短路徑是否存在，存在的情況最短路徑是多少，其次是不存在。<

19、;/p>　　問題分析　　實現(xiàn)本程序要解決以下幾個問題：　　5.1如何存儲一個有向圖。　　5.2如何在界面中輸出該有向圖。　　5.3如何定義起始源點。　　5.4如何選

20、擇出最短路徑。　　5.5找到的最短路徑如何輸出。　　數(shù)據(jù)結(jié)構(gòu)的選擇和概要設(shè)計　　1.數(shù)據(jù)結(jié)構(gòu)的選擇：　　在圖的結(jié)構(gòu)中，任意兩個頂點之間都可能存在關(guān)系，比線性表和樹要復(fù)雜。由于不存在嚴格的前后順序，因而不能采用簡單的數(shù)組來存儲圖;另一方面，如果采用鏈表，由于圖中各頂點的度數(shù)

21、不盡相同，最小度數(shù)和最大度數(shù)可能相差很大，如果按最大度數(shù)的頂點來設(shè)計鏈表的指針域，則會浪費很多存儲單元，反之，如果按照各個頂點設(shè)計不同的鏈表結(jié)點，則會給操作帶來很大的困難。　　在此我選用鄰接矩陣的存儲結(jié)構(gòu)。采用鄰接矩陣存儲，很容易判斷圖中兩個頂點是否相連，也容易求出各個頂點的度。不過任何事情都不是完美的，采用鄰接矩陣存儲圖時，測試其邊的數(shù)目，必須檢查邊二維數(shù)組的所有元素，時間復(fù)雜度為O（n2）,

22、這對于頂點很多而邊較少的圖（稀疏圖）是非常不合算的。　　以鄰接矩陣存儲有向圖。　　2.概要設(shè)計　　2.1對于最短路徑問題：　　最短路徑是在實際應(yīng)用中非常有用的工具，我們常見的兩種最短路徑是：

23、?。?）從某源點到其余各頂點之間的最短路徑。　　（2）每一段頂點之間的最短路徑　　在這里我們解決第一類問題。　　2.2 Dijkstra算法用于求最短路徑：　　Dijkstra算法是按路徑長度遞增的次序逐步產(chǎn)生源點到其他頂點間的最短路徑。算法建立一個頂點集合S，初始時該集

24、合只有源點V0，然后逐步將已求得最短路徑的頂點加入到集合中，直到全部頂點都在集合S中，算法結(jié)束。　　2..3 Dijkstra算法思想　　設(shè)cost[i,j]=0，S為已經(jīng)求得最短路徑的頂點集合，distance[i]數(shù)組的每個元素表示當前狀態(tài)下源點V0到Vi的最短路徑。算法如下：　　　1) 初始化：S={V0}

25、, distance[i]=cost[0,i]。　　2) 選擇一個終點Vj，滿足distance[j]=MIN{ distance[i]|Vi∈V-S}。　　3）把Vj加入到S中。　　4）修改distance數(shù)組元素，修改邏輯為對于所有不在S中的頂點Vi.　　if(dis

26、tance[j]+cost[i,j]< distance[i]) { distance[i]= distance[j] ]+cost[i,j] }　　重復(fù)操作2）、3）、4），直到全部頂點加入到S中。　　2.4 實現(xiàn)流程　　在任意圖中實現(xiàn)求最短路徑問題，第一步是要能

27、成功的在內(nèi)存中輸入圖的信息，圖的信息有兩個，一是頂點個數(shù)，二是每兩點之間的權(quán)值信息。當建立圖之后，對圖進行遍歷才能使用Dijkstra算法求出最短路徑；在完成了圖的建立之后，用Dijkstra算法的思想，從單源點開始，求出到各個頂點的最短路徑，并能夠?qū)崿F(xiàn)顯示功能。　　程序流程圖：　　(1) 輸入頂點個數(shù)n，邊的條數(shù)，

28、初始化鄰接矩陣。　　(2)初始化所每條邊的權(quán)值與D[h]中　　(3) ① 找出v0到圖中其他各點的最小值　?、?經(jīng)過改最小值的點到除它外其他各點的最小值　?、?直到s中的所有值全部被處理過，　　(4) 輸出各最短路徑的長度D[w]

29、　　算法的思想，從單源點開始，求出到各個頂點的最短路徑，并能夠?qū)崿F(xiàn)顯示功能。　　詳細設(shè)計和編碼　　3.1框架的建立　　typedef char VertexType;//定義圖的頂點為字符型 &l

30、t;/p>　　typedef int VRType; //頂點關(guān)系類型　　typedef int InfoType;//該弧相關(guān)信息　　typedef struct ArcCell{　　VRType adj;//權(quán)值 　　InfoType *i

31、nfo;//弧相關(guān)信息的指針　　}ArcCell;　　typedef struct{　　VertexType vexs[MAX_VERTEX_NUM];//一維數(shù)組，存儲頂點　　ArcCell arcs[MAX_VERTEX_NUM]

32、[MAX_VERTEX_NUM];//鄰接矩陣：二維數(shù)組，存儲邊和弧　　int vexnum,arcnum;//圖的當前頂點數(shù)和弧數(shù) 　　}MGrph;//鄰接矩陣表示的圖　　3.1.1頂點的定義typedef char VertexType;//定義圖的頂點為字符型頂點的最大個數(shù)25

33、　　3.1.2ArcCell arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM];二維數(shù)組用于存放鄰接矩陣，每個位置代表的值為圖中的權(quán)值，其余用無窮大3000表示。　　3.2點結(jié)構(gòu)體的定義　　/* 確定位置函數(shù) */

34、　int LocateVex(MGrph *G,VertexType v)　　{　　int j,b;　　for(b=0;b<G->vexnum;b++)//在所有頂點中尋找 　　if(

35、G->vexs[b]==v)//找到所找的頂點在b位置 　　{　　j=b;　　break;　　}//if</

36、p>　　return(j);　　} //LocateVex　　3.3創(chuàng)立帶權(quán)值有向圖　　首先輸入該有向圖的頂點數(shù)n,然后依次輸入各個頂點及邊長（輸入的頂點的序號應(yīng)該小于頂點的數(shù)目）。　　/* 有向圖的建立

37、 */　　void Creat_YG(MGrph *G)　　{　　int i,k,j,n;　　VertexType v1,v2;　　int w=1;

38、;　　printf("請輸入頂點個數(shù)和弧數(shù) 如括號里的方式（3,3）:");//讀入頂點個數(shù)和弧的個數(shù)　　scanf("%d,%d",&G->vexnum,&G->arcnum);//讀出邊和弧的信息　　printf("\n"

39、); //換行輸出　　for(i=0;i<G->vexnum;i++)　　{　　printf("請輸入圖的第%d個頂點:",w);//輸入指定的頂點　　w++;&l

40、t;/p>　　fflush(stdin);　　scanf("%c",&G->vexs[i]);　　printf("\n"); 　　}　　for(i=0;

41、i<G->vexnum;i++)　　for(j=0;j<G->vexnum;j++)　　{　　G->arcs[i][j].adj=INFINITY;　　G->arcs[i][j].info=NULL

42、;　　}　　for(k=0;k<G->arcnum;k++)　　{//輸入各弧并構(gòu)造鄰接矩陣 　　printf("請輸入邊的起點和終點和權(quán)值如（v1,v2,n）:");//起始點和終點和兩點之間對應(yīng)的權(quán)

43、值　　fflush(stdin);　　scanf("%c,%c,%d",&v1,&v2,&n);　　printf("\n"); 　　i=LocateVex(G,v1);//確定v1的位置

44、　　j=LocateVex(G,v2);//確定v2的位置 　　G->arcs[i][j].adj=n;//邊<v1,v2>的權(quán)值賦為1，如需要權(quán)值操作則相應(yīng)修改一下即可 　　G->arcs[i][j].info=NULL;//如需要有相關(guān)信息則相對應(yīng)輸入，在這里我設(shè)置為空 <p

45、>　　}//第二個for　　getchar();　　} //Creat_YG　　void juzhen(MGrph *G){//用矩陣來存儲并顯示出結(jié)果　　int i,j,k;　　pri

46、ntf("鄰接矩陣顯示：\n");　　printf("\t");　　for(i=0;i<G->vexnum;i++)　　printf("\t%5c",G->vexs[i]);　　for(j=0;

47、j<G->vexnum;j++)　　{　　printf("\n\n");　　printf("\t\%5c",G->vexs[j]);　　for(k=0;k<G->v

48、exnum;k++)　　{　　if(G->arcs[j][k].adj<INFINITY)　　printf("\t%5d",G->arcs[j][k].adj);　　else printf(&qu

49、ot;\t 3000"); //無權(quán)值的直接輸出最大值 　　}　　}　　3.4鄰接矩陣的顯示　　在圖的鄰接矩陣顯示中，分別利用for循環(huán)輸出了矩陣的行列標，使矩陣很明了。&

50、lt;/p>　　void juzhen(MGrph *G){//用矩陣來存儲并顯示出結(jié)果　　int i,j,k;　　printf("鄰接矩陣顯示：\n");　　printf("\t");　　for(i=0

51、;i<G->vexnum;i++)　　printf("\t%5c",G->vexs[i]);　　for(j=0;j<G->vexnum;j++)　　{　　printf("\n

52、\n");　　printf("\t\%5c",G->vexs[j]);　　for(k=0;k<G->vexnum;k++)　　{　　if(G->arcs[j][k].adj<

53、INFINITY)　　printf("\t%5d",G->arcs[j][k].adj);　　else printf("\t 3000"); //無權(quán)值的直接輸出最大值 　　}

54、;　　}　　}　　3.5遞歸函數(shù)應(yīng)用　　3.5.1思想是patn[]數(shù)組來表示前驅(qū)頂點的位置，然后遞歸輸出每個頂點的前驅(qū)　　void Short(MGrph

55、*G,int path[],int i,int w){　　//遞歸函數(shù)是用來輸出從源點出發(fā)到終點之前的頂點　　//思想是patn[]數(shù)組來表示前驅(qū)頂點的位置，然后遞歸輸出每個頂點的前驅(qū) 　　int k;　　k=path[i];<

56、/p>　　if(k!=w) Short(G,path,k,w );　　printf("%c,",G->vexs[k]);//輸出k位置的頂點值 　　}　　3.6 Dijkstra 算法實現(xiàn)最短路徑&

57、lt;p>　　設(shè)圖以鄰接矩陣cost存儲，矩陣中各元素的值為各邊的權(quán)值。頂點間無邊時其對應(yīng)權(quán)值用無窮大表示。從頂點V0到其它各頂點間的最短路徑的具體步驟如下：　　變量定義：　　定義整型數(shù)組S[],這是一個頂點集合，初始時該集合只有源點v0，然后逐步將以求得最短路徑的頂點加入到該集合中，直到全部頂點都在集合S中，

58、算法結(jié)束。定義兩個整型變量dis、mindis均用來標志圖中最短的那一條路徑。　　初始化：　　初始化dist數(shù)組的值即為cost數(shù)組中存放的權(quán)值。 dist[i]=cost[v0][i] 　　初始化求到每個頂點的最短路徑時都經(jīng)過v0頂點。path[i].pnode[0]=v0

59、　　初始化記錄經(jīng)過的頂點數(shù)都為0。 path[i].num=0; 　　初始化頂點集合s為空，即還未開始。s[i]=0; 　　源點的選擇:　　將v0頂點加入到頂點集合s中。 s[v0]=

60、1　　利用for循環(huán)選擇一個終點Vj,使其滿足V0到Vj距離最短，同時將Vj加入集合S中。　　根據(jù)j頂點調(diào)整當前的最短路徑，若滿足dist[i]> dist[j]+cost[j][i],則修改dist[i]的值。同時V0到Vi的最短路徑中經(jīng)過的頂點數(shù)加1，即path[i].num++; 并將經(jīng)過的頂點存入數(shù)組pnode即path[i].pnode[

61、path[i].num]=j 　　此時一趟求最短路徑完畢，將終點V1添加到路徑中。　　循環(huán)執(zhí)行d),e),f)操作，直到全部頂點加入到S中。　　上機調(diào)試　　4.1記錄調(diào)試過程中錯誤和問題的處理<p

62、>　　1) 當輸入格式不符合程序要求時，會出現(xiàn)循環(huán)　　2) 當兩頂點間沒有路徑時，權(quán)值為無窮大，但在本程序中只能用一個具體的數(shù)字2000代替抽象的無窮大。　　3) 在程序的調(diào)試過程可暫時多加一些輸出語句以便及時查看一下中間運行情況，并對程序規(guī)格說明作調(diào)整和改動。　　4.2算法的時間和空間性能分析</p

63、>　　4.2.1時間復(fù)雜度　　對于n個頂點的有向圖，求一個頂點到其他頂點的最短路徑的時間為O(n)，調(diào)整最短路徑的循環(huán)共執(zhí)行n-1次，是二層循環(huán)，所以，時間復(fù)雜度是O（n2）。　　4.2.2空間復(fù)雜度　　采用鄰接矩陣存儲有向圖，應(yīng)處理每兩個頂點之間的關(guān)系，所以空間復(fù)雜度為O（n2）。&

64、lt;/p>　　4.3算法設(shè)計、調(diào)試的經(jīng)驗和體會　　Dijkstra算法在上課的時候曾作為重點講過，所以在做查找最短路徑的算法時很流暢，但是在輸出最短路徑的時候遇到了很大的阻力。因為在定義結(jié)點時，使用的是結(jié)構(gòu)體數(shù)組，所以當處理V0到每個結(jié)點的最短路徑時，導致無法具體記錄經(jīng)過的頂點數(shù)，只能記錄源點、終點前一頂點以及終點。所以本程序在輸出最短路徑時有較大的瑕疵，還需進一步

65、修改。　　測試結(jié)果　　5.1測試結(jié)果：　　注意問題：　　1、輸入頂點個數(shù)：最大不超過25，請輸入羅馬數(shù)字，若輸入其他符號，無意義；&l

66、t;p>　　2、以“字母字母數(shù)字”的格式輸入圖的信息，輸入第一個字母為原點，第二個字母為終點，輸入“數(shù)字”為權(quán)值，最后輸入一個“字母”為頂點輸入。輸入完成；　　3、在輸入完成后，屏幕顯示鄰接矩陣與最短路徑。　　學習心得體會　　通過對本次課程設(shè)計的學習與交流，使我學習

67、到一部分很重要的關(guān)于編程方面思想，同時也獲得了部分學習其他學科的方法。學習重在于體會，體會這種學科給我?guī)淼乃伎迹o我?guī)碛蓽\入深的演算心得。做一次課程設(shè)計，不僅僅是為了完成某項任務(wù)，而在于是否能從這次任務(wù)中總結(jié)出一些處理同類任務(wù)的方法和技巧。每次全力的付出，都會有或多或少的收獲。通過對本次課程設(shè)計涉及的問題的分析和處理，了解到學習數(shù)據(jù)結(jié)構(gòu)對編程的技巧和思想方法。以前也了解過數(shù)據(jù)結(jié)構(gòu)相關(guān)的書籍，但沒有深入的學習，本次上機課程設(shè)計從選題上

68、也把學習的方法應(yīng)用其中，在編程時算法的理解和分析十分重要，首先的弄懂它的基本框架，用什么來算法來實現(xiàn)，最后通過查找部分資料，修改調(diào)試，總結(jié)心得，就是一種進步。　　參考文獻　　6.1：嚴蔚敏吳偉明編著的《數(shù)據(jù)結(jié)構(gòu)》（C語言版）　　6.2：楊曉波主編王弘王

69、聰華胡永副主編的　　《數(shù)據(jù)結(jié)構(gòu)實驗指導》（C語言版）　　附件：　　#include<stdio.h>　　#include<stdlib.h>　　#defin

70、e MAX_VERTEX_NUM 25 //最大頂點個數(shù)　　#define INFINITY 3000//最大值　　typedef char VertexType;//定義圖的頂點為字符型 　　typedef int VRType; //頂點關(guān)系類型　　typedef

71、int InfoType;//該弧相關(guān)信息　　typedef struct ArcCell{　　VRType adj;//權(quán)值 　　InfoType *info;//弧相關(guān)信息的指針　　}ArcCell;<

72、;p>　　typedef struct{　　VertexType vexs[MAX_VERTEX_NUM];//一維數(shù)組，存儲頂點　　ArcCell arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM];//鄰接矩陣：二維數(shù)組，存儲邊和弧　　int vexnum,arcnum;//圖的

73、當前頂點數(shù)和弧數(shù) 　　}MGrph;//鄰接矩陣表示的圖　　/* 確定位置函數(shù) */　　int LocateVex(MGrph *G,VertexType v)　　{</p

74、>　　int j,b;　　for(b=0;b<G->vexnum;b++)//在所有頂點中尋找 　　if(G->vexs[b]==v)//找到所找的頂點在b位置 　　{

75、　　j=b;　　break;　　}//if　　return(j);　　} //LocateVex

76、　/* 有向圖的建立 */　　void Creat_YG(MGrph *G)　　{　　int i,k,j,n;　　VertexType v1,v2;<p&g

77、t;　　int w=1;　　printf("請輸入頂點個數(shù)和弧數(shù) 如括號里的方式（3,3）:");//讀入頂點個數(shù)和弧的個數(shù)　　scanf("%d,%d",&G->vexnum,&G->arcnum);//讀出邊和弧的信息&l

78、t;p>　　printf("\n"); //換行輸出　　for(i=0;i<G->vexnum;i++)　　{　　printf("請輸入圖的第%d個頂點:",w);//輸入指定的頂點<p&

79、gt;　　w++;　　fflush(stdin);　　scanf("%c",&G->vexs[i]);　　printf("\n"); 　　}&

80、lt;/p>　　for(i=0;i<G->vexnum;i++)　　for(j=0;j<G->vexnum;j++)　　{　　G->arcs[i][j].adj=INFINITY;<p&g

81、t;　　G->arcs[i][j].info=NULL;　　}　　for(k=0;k<G->arcnum;k++)　　{//輸入各弧并構(gòu)造鄰接矩陣 　　printf("請輸入邊的起點和終點和權(quán)值如（v1,v

82、2,n）:");//起始點和終點和兩點之間對應(yīng)的權(quán)值　　fflush(stdin);　　scanf("%c,%c,%d",&v1,&v2,&n);　　printf("\n"); 　　i=Locate

83、Vex(G,v1);//確定v1的位置 　　j=LocateVex(G,v2);//確定v2的位置 　　G->arcs[i][j].adj=n;//邊<v1,v2>的權(quán)值賦為1，如需要權(quán)值操作則相應(yīng)修改一下即可 　　G->arcs[i][j].info=NULL;//如需要有相關(guān)信息則相對

84、應(yīng)輸入，在這里我設(shè)置為空 　　}//第二個for　　getchar();　　} //Creat_YG　　void juzhen(MGrph *G){//用矩陣來存儲并顯示出結(jié)果　　int i,

85、j,k;　　printf("鄰接矩陣顯示：\n");　　printf("\t");　　for(i=0;i<G->vexnum;i++)　　printf("\t%5c",G->vexs[i]);&

86、lt;/p>　　for(j=0;j<G->vexnum;j++)　　{　　printf("\n\n");　　printf("\t\%5c",G->vexs[j]);&

87、lt;p>　　for(k=0;k<G->vexnum;k++)　　{　　if(G->arcs[j][k].adj<INFINITY)　　printf("\t%5d",G->arcs[j][k].adj);</p&g

88、t;　　else printf("\t 3000"); //無權(quán)值的直接輸出最大值 　　}　　}　　}

89、　　void Short(MGrph *G,int path[],int i,int w){　　//遞歸函數(shù)是用來輸出從源點出發(fā)到終點之前的頂點　　//思想是patn[]數(shù)組來表示前驅(qū)頂點的位置，然后遞歸輸出每個頂點的前驅(qū) 　　int k;<p&

90、gt;　　k=path[i];　　if(k!=w) Short(G,path,k,w );　　printf("%c,",G->vexs[k]);//輸出k位置的頂點值 　　}　　void ShortestP

91、ath(MGrph *G,int w){ //Dijkstrs算法應(yīng)用　　int i,k,m,n,min;　　int final[30],path[30],D[30];//定義三個數(shù)組，final[]標記該頂點是否在最短路徑上　　//path[]用來記錄頂點的前驅(qū)頂點的位置，D[]是用來記錄從源點到該點的最短路

92、徑長度 　　for(i=0;i<G->vexnum;i++)　　{　　path[i]=w;//首先把所有頂點的前驅(qū)頂點的位置賦值為w位置，也就是源點的位置　　final[i]=0;//這是一個標記數(shù)組，一開始所有頂點位置

93、對應(yīng)的數(shù)組值全部標記為0 　　D[i]=G->arcs[w][i].adj;//D[]是用來記錄最短路徑的長度，一開始把所有頂點到源點的的距離賦值給它 　　}　　D[w]=0;final[w]=1;path[w]=-100;//源點位置的D[w]為0，final[w]=

94、1標記已經(jīng)入集合，path[w]=-100，表示該前驅(qū)為-100 　　for(m=1;m<G->vexnum;m++)　　{　　min=INFINITY;//首先賦值為機內(nèi)最大值 　　for(k=0;k<G->

95、vexnum;k++)　　{　　if(!final[k])　　if(D[k]<min)　　{　　i=k;<

96、;/p>　　min=D[k];//最短路徑長度　　}　　} 　　final[i]=1;　　for(n=0;n<G->vexnum;n++)</p&g

97、t;　　if(!final[n]&&(min+G->arcs[i][n].adj)<D[n])　　{　　D[n]=min+G->arcs[i][n].adj;　　path[n]=i;<p&

98、gt;　　}//if　　} //for 　　for(m=0;m<G->vexnum;m++){　　if(final[m]==1&&m!=w)　　{printf(&qu

99、ot;\t從%c到%c的最短路徑長度為：%d\t路徑是：",G->vexs[w],G->vexs[m],D[m]);//輸出最大值時則表示兩點之間沒有最短路徑　　Short(G,path,m,w);　　printf("%c",G->vexs[m]);　　printf

100、("\n");　　}　　else printf("\t從%c到%c沒有不存在路徑！\n",G->vexs[w],G->vexs[m]);//判斷是否存在最短路徑　　}

101、　　}　　main(){　　MGrph m;　　VertexType ch;　　int j;<

102、;/p>　　Creat_YG(&m);　　juzhen(&m);　　printf("\n請輸入要開始的頂點:");　　scanf("%c",&ch);　　j=LocateVex(&

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

溫馨提示

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

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

文檔簡介

溫馨提示

最新文檔

評論

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

文檔簡介

溫馨提示

最新文檔

評論

免費下載