數(shù)據(jù)結(jié)構(gòu)課程設(shè)計報告--dijkstra算法求最短路徑(編輯修改稿)
2025-05-08 22:48 本頁面
【文章內(nèi)容簡介】 j)。} //LocateVex首先輸入該有向圖的頂點數(shù)n,然后依次輸入各個頂點及邊長（輸入的頂點的序號應(yīng)該小于頂點的數(shù)目）。/* 有向圖的建立 */void Creat_YG(MGrph *G){ int i,k,j,n。 VertexType v1,v2。 int w=1。 printf(請輸入頂點個數(shù)和弧數(shù) 如括號里的方式（3,3）:)。//讀入頂點個數(shù)和弧的個數(shù) scanf(%d,%d,amp。Gvexnum,amp。Garum)。//讀出邊和弧的信息 printf(\n)。 //換行輸出 for(i=0。iGvexnum。i++) { printf(請輸入圖的第%d個頂點:,w)。//輸入指定的頂點 w++。 fflush(stdin)。 scanf(%c,amp。Gvexs[i])。 printf(\n)。 } for(i=0。iGvexnum。i++) for(j=0。jGvexnum。j++) { Garcs[i][j].adj=INFINITY。 Garcs[i][j].info=NULL。 } for(k=0。kGarum。k++) {//輸入各弧并構(gòu)造鄰接矩陣 printf(請輸入邊的起點和終點和權(quán)值如（v1,v2,n）:)。//起始點和終點和兩點之間對應(yīng)的權(quán)值 fflush(stdin)。 scanf(%c,%c,%d,amp。v1,amp。v2,amp。n)。 printf(\n)。 i=LocateVex(G,v1)。//確定v1的位置 j=LocateVex(G,v2)。//確定v2的位置 Garcs[i][j].adj=n。//邊v1,v2的權(quán)值賦為1，如需要權(quán)值操作則相應(yīng)修改一下即可 Garcs[i][j].info=NULL。//如需要有相關(guān)信息則相對應(yīng)輸入，在這里我設(shè)置為空 }//第二個forgetchar()。} //Creat_YGvoid juzhen(MGrph *G){//用矩陣來存儲并顯示出結(jié)果 int i,j,k。 printf(鄰接矩陣顯示：\n)。 printf(\t)。 for(i=0。iGvexnum。i++) printf(\t%5c,Gvexs[i])。 for(j=0。jGvexnum。j++) { printf(\n\n)。 printf(\t\%5c,Gvexs[j])。 for(k=0。kGvexnum。k++) { if(Garcs[j][k].adjINFINITY) printf(\t%5d,Garcs[j][k].adj)。 else printf(\t 3000)。 //無權(quán)值的直接輸出最大值 } }在圖的鄰接矩陣顯示中，分別利用for循環(huán)輸出了矩陣的行列標(biāo)，使矩陣很明了。void juzhen(MGrph *G){//用矩陣來存儲并顯示出結(jié)果 int i,j,k。 printf(鄰接矩陣顯示：\n)。 printf(\t)。 for(i=0。iGvexnum。i++) printf(\t%5c,Gvexs[i])。 for(j=0。jGvexnum。j++) { printf(\n\n)。 printf(\t\%5c,Gvexs[j])。 for(k=0。kGvexnum。k++) { if(Garcs[j][k].adjINFINITY) printf(\t%5d,Garcs[j][k].adj)。 else printf(\t 3000)。 //無權(quán)值的直接輸出最大值 } }}[]數(shù)組來表示前驅(qū)頂點的位置，然后遞歸輸出每個頂點的前驅(qū)void Short(MGrph *G,int path[],int i,int w){ //遞歸函數(shù)是用來輸出從源點出發(fā)到終點之前的頂點 //思想是patn[]數(shù)組來表示前驅(qū)頂點的位置，然后遞歸輸出每個頂點的前驅(qū) int k。 k=path[i]。 if(k!=w) Short(G,path,k,w )。 printf(%c,Gvexs[k])。//輸出k位置的頂點值 } Dijkstra 算法實現(xiàn)最短路徑設(shè)圖以鄰接矩陣cost存儲，矩陣中各元素的值為各邊的權(quán)值。頂點間無邊時其對應(yīng)權(quán)值用無窮大表示。從頂點V0到其它各頂點間的最短路徑的具體步驟如下：a) 變量定義：定義整型數(shù)組S[],這是一個頂點集合，初始時該集合只有源點v0，然后逐步將以求得最短路徑的頂點加入到該集合中，直到全部頂點都在集合S中，算法結(jié)束。定義兩個整型變量dis、mindis均用來標(biāo)志圖中最短的那一條路徑。b) 初始化：初始化dist數(shù)組的值即為cost數(shù)組中存放的權(quán)值。 dist[i]=cost[v0][i] 初始化求到每個頂點的最短路徑時都經(jīng)過v0頂點。path[i].pnode[0]=v0 初始化記錄經(jīng)過的頂點數(shù)都為0。 path[i].num=0。 初始化頂點集合s為空，即還未開始。 s[
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號-1