數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告--dijkstra算法求最短路徑-文庫吧
2025-01-06 16:13 本頁面
【正文】 12第1章 問題分析與任務(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)開始求最短路徑，并顯示出來。2. 原始數(shù)據(jù)的輸入格式：：+逗號+數(shù)字+回車 +回車3. 實(shí)現(xiàn)功能4. 測試用例：輸入頂點(diǎn)；邊值信息輸出結(jié)果：最短路徑是否存在，存在的情況最短路徑是多少，其次是不存在。5. 問題分析實(shí)現(xiàn)本程序要解決以下幾個(gè)問題：。第2章 數(shù)據(jù)結(jié)構(gòu)的選擇和概要設(shè)計(jì)： 在圖的結(jié)構(gòu)中，任意兩個(gè)頂點(diǎn)之間都可能存在關(guān)系，比線性表和樹要復(fù)雜。由于不存在嚴(yán)格的前后順序，因而不能采用簡單的數(shù)組來存儲(chǔ)圖。另一方面，如果采用鏈表，由于圖中各頂點(diǎn)的度數(shù)不盡相同，最小度數(shù)和最大度數(shù)可能相差很大，如果按最大度數(shù)的頂點(diǎn)來設(shè)計(jì)鏈表的指針域，則會(huì)浪費(fèi)很多存儲(chǔ)單元，反之，如果按照各個(gè)頂點(diǎn)設(shè)計(jì)不同的鏈表結(jié)點(diǎn)，則會(huì)給操作帶來很大的困難。 在此我選用鄰接矩陣的存儲(chǔ)結(jié)構(gòu)。采用鄰接矩陣存儲(chǔ)，很容易判斷圖中兩個(gè)頂點(diǎn)是否相連，也容易求出各個(gè)頂點(diǎn)的度。不過任何事情都不是完美的，采用鄰接矩陣存儲(chǔ)圖時(shí)，測試其邊的數(shù)目，必須檢查邊二維數(shù)組的所有元素，時(shí)間復(fù)雜度為O（n2）,這對于頂點(diǎn)很多而邊較少的圖（稀疏圖）是非常不合算的。以鄰接矩陣存儲(chǔ)有向圖。：最短路徑是在實(shí)際應(yīng)用中非常有用的工具，我們常見的兩種最短路徑是：（1）從某源點(diǎn)到其余各頂點(diǎn)之間的最短路徑。（2）每一段頂點(diǎn)之間的最短路徑在這里我們解決第一類問題。 Dijkstra算法用于求最短路徑：Dijkstra算法是按路徑長度遞增的次序逐步產(chǎn)生源點(diǎn)到其他頂點(diǎn)間的最短路徑。算法建立一個(gè)頂點(diǎn)集合S，初始時(shí)該集合只有源點(diǎn)V0，然后逐步將已求得最短路徑的頂點(diǎn)加入到集合中，直到全部頂點(diǎn)都在集合S中，算法結(jié)束。 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的最短路徑。算法如下： 1) 初始化：S={V0}, distance[i]=cost[0,i]。2) 選擇一個(gè)終點(diǎn)Vj，滿足distance[j]=MIN{ distance[i]|Vi∈VS}。3）把Vj加入到S中。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中。輸入頂點(diǎn)名稱輸入每條邊的信息返回每個(gè)結(jié)點(diǎn) 的位置創(chuàng)建圖Dijkstra算法的實(shí)現(xiàn)D[w]n輸出源點(diǎn)與其他點(diǎn)最短距離開始輸入頂點(diǎn)邊個(gè)數(shù)結(jié)束 實(shí)現(xiàn)流程在任意圖中實(shí)現(xiàn)求最短路徑問題，第一步是要能成功的在內(nèi)存中輸入圖的信息，圖的信息有兩個(gè)，一是頂點(diǎn)個(gè)數(shù)，二是每兩點(diǎn)之間的權(quán)值信息。當(dāng)建立圖之后，對圖進(jìn)行遍歷才能使用Dijkstra算法求出最短路徑；在完成了圖的建立之后，用Dijkstra算法的思想，從單源點(diǎn)開始，求出到各個(gè)頂點(diǎn)的最短路徑，并能夠?qū)崿F(xiàn)顯示功能。 程序流程圖：(1) 輸入頂點(diǎn)個(gè)數(shù)n，邊的條數(shù)，初始化鄰接矩陣。(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)顯示功能。第3章 詳細(xì)設(shè)計(jì)和編碼typedef char VertexType。//定義圖的頂點(diǎn)為字符型 typedef int VRType。 //頂點(diǎn)關(guān)系類型typedef int InfoType。//該弧相關(guān)信息 typedef struct ArcCell{ VRType adj。//權(quán)值 InfoType *info。//弧相關(guān)信息的指針}ArcCell。 typedef struct{ VertexType vexs[MAX_VERTEX_NUM]。//一維數(shù)組，存儲(chǔ)頂點(diǎn) ArcCell arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM]。//鄰接矩陣 ：二維數(shù)組，存儲(chǔ)邊和弧 int vexnum,arum。//圖的當(dāng)前頂點(diǎn)數(shù)和弧數(shù) }MGrph。 //鄰接矩陣表示的圖 char VertexType。//定義圖的頂點(diǎn)為字符型 頂點(diǎn)的最大個(gè)數(shù)25 arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM]。二維數(shù)組用于存放鄰接矩陣，每個(gè)位置代表的值為圖中的權(quán)值，其余用無窮大3000表示。/* 確定位置函數(shù) */int LocateVex(MGrph *G,VertexType v){ int j,b。 for(b=0。bGvexnum。b++)//在所有頂點(diǎn)中尋找 if(Gvexs[b]==v)//找到所找的頂點(diǎn)在b位置 { j=b。 break。 }//if return(
范文總結(jié)相關(guān)推薦
鄂ICP備17016276號-1