數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告--dijkstra算法求最短路徑-在線瀏覽
2025-05-29 22:48本頁(yè)面
【正文】 12附錄12第1章 問(wèn)題分析與任務(wù)定義 課程設(shè)計(jì)題目：：采用適當(dāng)?shù)拇鎯?chǔ)結(jié)構(gòu)實(shí)現(xiàn)帶權(quán)有向圖的存儲(chǔ)，建立，輸入、顯示，以及使用Dijkstra算法，尋找和輸出帶權(quán)有向圖中某個(gè)源點(diǎn)到其余各點(diǎn)的最短路徑：采用適當(dāng)?shù)拇鎯?chǔ)結(jié)構(gòu)實(shí)現(xiàn)帶權(quán)有向圖的存儲(chǔ)，建立，輸入、顯示，以及使用Dijkstra算法。：建立圖的存儲(chǔ)模塊，建立圖的輸出模塊，在建圖后從單源點(diǎn)開(kāi)始求最短路徑，并顯示出來(lái)。5. 問(wèn)題分析實(shí)現(xiàn)本程序要解決以下幾個(gè)問(wèn)題：。由于不存在嚴(yán)格的前后順序，因而不能采用簡(jiǎn)單的數(shù)組來(lái)存儲(chǔ)圖。 在此我選用鄰接矩陣的存儲(chǔ)結(jié)構(gòu)。不過(guò)任何事情都不是完美的，采用鄰接矩陣存儲(chǔ)圖時(shí)，測(cè)試其邊的數(shù)目，必須檢查邊二維數(shù)組的所有元素，時(shí)間復(fù)雜度為O（n2）,這對(duì)于頂點(diǎn)很多而邊較少的圖（稀疏圖）是非常不合算的。：最短路徑是在實(shí)際應(yīng)用中非常有用的工具，我們常見(jiàn)的兩種最短路徑是：（1）從某源點(diǎn)到其余各頂點(diǎn)之間的最短路徑。 Dijkstra算法用于求最短路徑：Dijkstra算法是按路徑長(zhǎng)度遞增的次序逐步產(chǎn)生源點(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的最短路徑。2) 選擇一個(gè)終點(diǎn)Vj，滿足distance[j]=MIN{ distance[i]|Vi∈VS}。4）修改distance數(shù)組元素，修改邏輯為對(duì)于所有不在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中。當(dāng)建立圖之后，對(duì)圖進(jìn)行遍歷才能使用Dijkstra算法求出最短路徑；在完成了圖的建立之后，用Dijkstra算法的思想，從單源點(diǎn)開(kāi)始，求出到各個(gè)頂點(diǎn)的最短路徑，并能夠?qū)崿F(xiàn)顯示功能。(2)初始化所每條邊的權(quán)值與D[h]中(3) ① 找出v0到圖中其他各點(diǎn)的最小值 ② 經(jīng)過(guò)改最小值的點(diǎn)到除它外其他各點(diǎn)的最小值 ③ 直到s中的所有值全部被處理過(guò)， (4) 輸出各最短路徑的長(zhǎng)度D[w]算法的思想，從單源點(diǎn)開(kāi)始，求出到各個(gè)頂點(diǎn)的最短路徑，并能夠?qū)崿F(xiàn)顯示功能。//定義圖的頂點(diǎn)為字符型 typedef int VRType。//該弧相關(guān)信息 typedef struct ArcCell{ VRType adj。//弧相關(guān)信息的指針}ArcCell。//一維數(shù)組，存儲(chǔ)頂點(diǎn) ArcCell arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM]。//圖的當(dāng)前頂點(diǎn)數(shù)和弧數(shù) }MGrph。//定義圖的頂點(diǎn)為字符型 頂點(diǎn)的最大個(gè)數(shù)25 arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM]。/* 確定位置函數(shù) */int LocateVex(MGrph *G,VertexType v){ int j,b。bGvexnum。 break。} //LocateVex首先輸入該有向圖的頂點(diǎn)數(shù)n,然后依次輸入各個(gè)頂點(diǎn)及邊長(zhǎng)（輸入的頂點(diǎn)的序號(hào)應(yīng)該小于頂點(diǎn)的數(shù)目）。 VertexType v1,v2。 printf(請(qǐng)輸入頂點(diǎn)個(gè)數(shù)和弧數(shù) 如括號(hào)里的方式（3,3）:)。Gvexnum,amp。//讀出邊和弧的信息 printf(\n)。iGvexnum。//輸入指定的頂點(diǎn) w++。 scanf(%c,amp。 printf(\n)。iGvexnum。jGvexnum。 Garcs[i][j].info=NULL。kGarum。//起始點(diǎn)和終點(diǎn)和兩點(diǎn)之間對(duì)應(yīng)的權(quán)值 fflush(stdin)。v1,amp。n)。 i=LocateVex(G,v1)。//確定v2的位置 Garcs[i][j].adj=n。//如需要有相關(guān)信息則相對(duì)應(yīng)輸入，在這里我設(shè)置為空 }//第二個(gè)forgetchar()。 printf(鄰接矩陣顯示：\n)。 for(i=0。i++) printf(\t%5c,Gvexs[i])。jGvexnum。 printf(\t\%5c,Gvexs[j])。kGvexnum。 else printf(\t 3000)。void juzhen(MGrph *G){//用矩陣來(lái)存儲(chǔ)并顯示出結(jié)果 int i,j,k。 printf(\t)。iGvexnum。 for(j=0。j++) { printf(\n\n)。 for(k=0。k++) { if(Garcs[j][k].adjINFINITY) printf(\t%5d,Garcs[j][k].adj)。 //無(wú)權(quán)值的直接輸出最大值 } }}[]數(shù)組來(lái)表示前驅(qū)頂點(diǎn)的位置，然后
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1