數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告--dijkstra算法求最短路徑-預(yù)覽頁
【正文】 出帶權(quán)有向圖中某個(gè)源點(diǎn)到其余各點(diǎn)的最短路徑：采用適當(dāng)?shù)拇鎯?chǔ)結(jié)構(gòu)實(shí)現(xiàn)帶權(quán)有向圖的存儲(chǔ)，建立，輸入、顯示，以及使用Dijkstra算法。5. 問題分析實(shí)現(xiàn)本程序要解決以下幾個(gè)問題：。 在此我選用鄰接矩陣的存儲(chǔ)結(jié)構(gòu)。：最短路徑是在實(shí)際應(yīng)用中非常有用的工具，我們常見的兩種最短路徑是：（1）從某源點(diǎn)到其余各頂點(diǎn)之間的最短路徑。 2..3 Dijkstra算法思想設(shè)cost[i,j]=0，S為已經(jīng)求得最短路徑的頂點(diǎn)集合，distance[i]數(shù)組的每個(gè)元素表示當(dāng)前狀態(tài)下源點(diǎn)V0到Vi的最短路徑。4）修改distance數(shù)組元素，修改邏輯為對于所有不在S中的頂點(diǎn)Vi.if(distance[j]+cost[i,j] distance[i]) { distance[i]= distance[j] ]+cost[i,j] }5) 重復(fù)操作2）、3）、4），直到全部頂點(diǎn)加入到S中。(2)初始化所每條邊的權(quán)值與D[h]中(3) ① 找出v0到圖中其他各點(diǎn)的最小值 ② 經(jīng)過改最小值的點(diǎn)到除它外其他各點(diǎn)的最小值 ③ 直到s中的所有值全部被處理過， (4) 輸出各最短路徑的長度D[w]算法的思想，從單源點(diǎn)開始，求出到各個(gè)頂點(diǎn)的最短路徑，并能夠?qū)崿F(xiàn)顯示功能。//該弧相關(guān)信息 typedef struct ArcCell{ VRType adj。//一維數(shù)組，存儲(chǔ)頂點(diǎn) ArcCell arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM]。//定義圖的頂點(diǎn)為字符型 頂點(diǎn)的最大個(gè)數(shù)25 arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM]。bGvexnum。} //LocateVex首先輸入該有向圖的頂點(diǎn)數(shù)n,然后依次輸入各個(gè)頂點(diǎn)及邊長（輸入的頂點(diǎn)的序號(hào)應(yīng)該小于頂點(diǎn)的數(shù)目）。 printf(請輸入頂點(diǎn)個(gè)數(shù)和弧數(shù) 如括號(hào)里的方式（3,3）:)。//讀出邊和弧的信息 printf(\n)。//輸入指定的頂點(diǎn) w++。 printf(\n)。jGvexnum。kGarum。v1,amp。 i=LocateVex(G,v1)。//如需要有相關(guān)信息則相對應(yīng)輸入，在這里我設(shè)置為空 }//第二個(gè)forgetchar()。 for(i=0。jGvexnum。kGvexnum。void juzhen(MGrph *G){//用矩陣來存儲(chǔ)并顯示出結(jié)果 int i,j,k。iGvexnum。j++) { printf(\n\n)。k++) { if(Garcs[j][k].adjINFINITY) printf(\t%5d,Garcs[j][k].adj)。 if(k!=w) Short(G,path,k,w )。從頂點(diǎn)V0到其它各頂點(diǎn)間的最短路徑的具體步驟如下：a) 變量定義：定義整型數(shù)組S[],這是一個(gè)頂點(diǎn)集合，初始時(shí)該集合只有源點(diǎn)v0，然后逐步將以求得最短路徑的頂點(diǎn)加入到該集合中，直到全部頂點(diǎn)都在集合S中，算法結(jié)束。path[i].pnode[0]=v0 初始化記錄經(jīng)過的頂點(diǎn)數(shù)都為0。 c) 源點(diǎn)的選擇:將v0頂點(diǎn)加入到頂點(diǎn)集合s中。 并將經(jīng)過的頂點(diǎn)存入數(shù)組pnode即path[i].pnode[path[i].num]=j f) 此時(shí)一趟求最短路徑完畢，將終點(diǎn)V1添加到路徑中。對于n個(gè)頂點(diǎn)的有向圖，求一個(gè)頂點(diǎn)到其他頂點(diǎn)的最短路徑的時(shí)間為O(n)，調(diào)整最短路徑的循環(huán)共執(zhí)行n1次，是二層循環(huán)，所以，時(shí)間復(fù)雜度是O（n2）。所以本程序在輸出最短路徑時(shí)有較大的瑕疵，還需進(jìn)一步修改。學(xué)習(xí)重在于體會(huì)，體會(huì)這種學(xué)科給我?guī)淼乃伎?，給我?guī)碛蓽\入深的演算心得。以前也了解過數(shù)據(jù)結(jié)構(gòu)相關(guān)的書籍，但沒有深入的學(xué)習(xí)，本次上機(jī)課程設(shè)計(jì)從選題上也把學(xué)習(xí)的方法應(yīng)用其中，在編程時(shí)算法的理解和分析十分重要，首先的弄懂它的基本框架，用什么來算法來實(shí)現(xiàn)，最后通過查找部分資料，修改調(diào)試，總結(jié)心得，就是一種進(jìn)步。//該弧相關(guān)信息 typedef struct ArcCell{ VRType adj。//一維數(shù)組，存儲(chǔ)頂點(diǎn) ArcCell arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM]。 for(b=0。 }//if return(j)。 printf(請輸入頂點(diǎn)個(gè)數(shù)和弧數(shù) 如括號(hào)里的方式（3,3）:)。//讀出邊和弧的信息 printf(\n)。//輸入指定的頂點(diǎn) w++。 printf(\n)。jGvexnum。kGarum。v1,amp。 i=LocateVex(G,v1)。//如需要有相關(guān)信息則相對應(yīng)輸入，在這里我設(shè)置為空 }//第二個(gè)forgetchar()。 for(i=0。jGvexnum。kGvexnum。 k=path[i]。 int final[30],path[30],D[30]。//首先把所有頂點(diǎn)的前驅(qū)頂點(diǎn)的位置賦值為w位置，也就是源點(diǎn)的位置 final[i]=0。path[w]=100。//首先賦值為機(jī)內(nèi)最大值 for(k=0。//最短路徑長度 } } final[i]=1。amp。mGvexnum。//輸出最大值時(shí)則表示兩點(diǎn)之間沒有最短路徑 Short(G,path,m,w)。//判斷是否存在最短路徑 } } main(){ MGrph m。m)。 scanf(%c,amp。 getchar()。 }17
范文總結(jié)相關(guān)推薦
鄂ICP備17016276號(hào)-1