數(shù)據(jù)結(jié)構(gòu)課程設(shè)計報告--dijkstra算法求最短路徑-文庫吧資料
2025-04-17 22:48本頁面
【正文】 第5章 測試結(jié)果：注意問題：輸入頂點個數(shù)：最大不超過25，請輸入羅馬數(shù)字，若輸入其他符號，無意義；以“字母 字母 數(shù)字”的格式輸入圖的信息，輸入第一個字母為原點，第二個字母為終點，輸入“數(shù)字”為權(quán)值，最后輸入一個“字母”為頂點輸入。因為在定義結(jié)點時，使用的是結(jié)構(gòu)體數(shù)組，所以當處理V0到每個結(jié)點的最短路徑時，導致無法具體記錄經(jīng)過的頂點數(shù)，只能記錄源點、終點前一頂點以及終點。 采用鄰接矩陣存儲有向圖，應處理每兩個頂點之間的關(guān)系，所以空間復雜度為O（n2）。3) 在程序的調(diào)試過程可暫時多加一些輸出語句以便及時查看一下中間運行情況，并對程序規(guī)格說明作調(diào)整和改動。g) 循環(huán)執(zhí)行d),e),f)操作，直到全部頂點加入到S中。同時V0到Vi的最短路徑中經(jīng)過的頂點數(shù)加1，即path[i].num++。 s[v0]=1d) 利用for循環(huán)選擇一個終點Vj,使其滿足V0到Vj距離最短，同時將Vj加入集合S中。 s[i]=0。 path[i].num=0。 dist[i]=cost[v0][i] 初始化求到每個頂點的最短路徑時都經(jīng)過v0頂點。定義兩個整型變量dis、mindis均用來標志圖中最短的那一條路徑。頂點間無邊時其對應權(quán)值用無窮大表示。 printf(%c,Gvexs[k])。 k=path[i]。 else printf(\t 3000)。kGvexnum。 printf(\t\%5c,Gvexs[j])。jGvexnum。i++) printf(\t%5c,Gvexs[i])。 for(i=0。 printf(鄰接矩陣顯示：\n)。 //無權(quán)值的直接輸出最大值 } }在圖的鄰接矩陣顯示中，分別利用for循環(huán)輸出了矩陣的行列標，使矩陣很明了。k++) { if(Garcs[j][k].adjINFINITY) printf(\t%5d,Garcs[j][k].adj)。 for(k=0。j++) { printf(\n\n)。 for(j=0。iGvexnum。 printf(\t)。} //Creat_YGvoid juzhen(MGrph *G){//用矩陣來存儲并顯示出結(jié)果 int i,j,k。//邊v1,v2的權(quán)值賦為1，如需要權(quán)值操作則相應修改一下即可 Garcs[i][j].info=NULL。//確定v1的位置 j=LocateVex(G,v2)。 printf(\n)。v2,amp。 scanf(%c,%c,%d,amp。k++) {//輸入各弧并構(gòu)造鄰接矩陣 printf(請輸入邊的起點和終點和權(quán)值如（v1,v2,n）:)。 } for(k=0。j++) { Garcs[i][j].adj=INFINITY。i++) for(j=0。 } for(i=0。Gvexs[i])。 fflush(stdin)。i++) { printf(請輸入圖的第%d個頂點:,w)。 //換行輸出 for(i=0。Garum)。//讀入頂點個數(shù)和弧的個數(shù) scanf(%d,%d,amp。 int w=1。/* 有向圖的建立 */void Creat_YG(MGrph *G){ int i,k,j,n。 }//if return(j)。b++)//在所有頂點中尋找 if(Gvexs[b]==v)//找到所找的頂點在b位置 { j=b。 for(b=0。二維數(shù)組用于存放鄰接矩陣，每個位置代表的值為圖中的權(quán)值，其余用無窮大3000表示。 //鄰接矩陣表示的圖 char VertexType。//鄰接矩陣 ：二維數(shù)組，存儲邊和弧 int vexnum,arum。 typedef struct{ VertexType vexs[MAX_VERTEX_NUM]。//權(quán)值 InfoType *info。 //頂點關(guān)系類型typedef int InfoType。第3章 詳細設(shè)計和編碼typedef char VertexType。 程序流程圖：(1) 輸入頂點個數(shù)n，邊的條數(shù)，初始化鄰接矩陣。輸入頂點名稱輸入每條邊的信息返回每個結(jié)點 的位置創(chuàng)建圖Dijkstra算法的實現(xiàn)D[w]n輸出源點與其他點最短距離開始輸入頂點邊個數(shù)結(jié)束 實現(xiàn)流程在任意圖中實現(xiàn)求最短路徑問題，第一步是要能成功的在內(nèi)存中輸入圖的信息，圖的信息有兩個，一是頂點個數(shù)，二是每兩點之間的權(quán)值信息。3）把Vj加入到S中。算法如下： 1) 初始化：S={V0}, distance[i]=cost[0,i]。算法建立一個頂點集合S，初始時該集合只有源點V0，然后逐步將已求得最短路徑的頂點加入到集合中，直到全部頂點都在集合S中，算法結(jié)束。（2）每一段頂點之間的最短路徑在這里我們解決第一類問題。以鄰接矩陣存儲有向圖。采用鄰接矩陣存儲，很容易判斷圖中兩個頂點是否相連，也容易求出各個頂點的度。另一方面，如果采用鏈表，由于圖中各頂點的度數(shù)不盡相同，最小度數(shù)和最大度數(shù)可能相差很大，如果按最大度數(shù)的頂點來設(shè)計鏈表的指針域，則會浪費很多存儲單元，反之，如果按照各個頂點設(shè)計不同的鏈表結(jié)點，則會給操作帶來很大的困難。第2章 數(shù)據(jù)結(jié)
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號-1