數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告--dijkstra算法求最短路徑-資料下載頁
2025-01-21 16:13本頁面
【正文】 s[i][j].adj=INFINITY。 Garcs[i][j].info=NULL。 } for(k=0。kGarum。k++) {//輸入各弧并構(gòu)造鄰接矩陣 printf(請(qǐng)輸入邊的起點(diǎn)和終點(diǎn)和權(quán)值如（v1,v2,n）:)。//起始點(diǎn)和終點(diǎn)和兩點(diǎn)之間對(duì)應(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)信息則相對(duì)應(yīng)輸入，在這里我設(shè)置為空 }//第二個(gè)forgetchar()。} //Creat_YGvoid juzhen(MGrph *G){//用矩陣來存儲(chǔ)并顯示出結(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)值的直接輸出最大值 } }}void Short(MGrph *G,int path[],int i,int w){ //遞歸函數(shù)是用來輸出從源點(diǎn)出發(fā)到終點(diǎn)之前的頂點(diǎn) //思想是patn[]數(shù)組來表示前驅(qū)頂點(diǎn)的位置，然后遞歸輸出每個(gè)頂點(diǎn)的前驅(qū) int k。 k=path[i]。 if(k!=w) Short(G,path,k,w )。 printf(%c,Gvexs[k])。//輸出k位置的頂點(diǎn)值 }void ShortestPath(MGrph *G,int w){ //Dijkstrs算法應(yīng)用 int i,k,m,n,min。 int final[30],path[30],D[30]。 //定義三個(gè)數(shù)組，final[]標(biāo)記該頂點(diǎn)是否在最短路徑上 //path[]用來記錄頂點(diǎn)的前驅(qū)頂點(diǎn)的位置，D[]是用來記錄從源點(diǎn)到該點(diǎn)的最短路徑長度 for(i=0。iGvexnum。i++) { path[i]=w。//首先把所有頂點(diǎn)的前驅(qū)頂點(diǎn)的位置賦值為w位置，也就是源點(diǎn)的位置 final[i]=0。//這是一個(gè)標(biāo)記數(shù)組，一開始所有頂點(diǎn)位置對(duì)應(yīng)的數(shù)組值全部標(biāo)記為0 D[i]=Garcs[w][i].adj。//D[]是用來記錄最短路徑的長度，一開始把所有頂點(diǎn)到源點(diǎn)的的距離賦值給它 } D[w]=0。final[w]=1。path[w]=100。//源點(diǎn)位置的D[w]為0，final[w]=1標(biāo)記已經(jīng)入集合，path[w]=100，表示該前驅(qū)為100 for(m=1。mGvexnum。m++) { min=INFINITY。//首先賦值為機(jī)內(nèi)最大值 for(k=0。kGvexnum。k++) { if(!final[k]) if(D[k]min) { i=k。 min=D[k]。//最短路徑長度 } } final[i]=1。 for(n=0。nGvexnum。n++) if(!final[n]amp。amp。(min+Garcs[i][n].adj)D[n]) { D[n]=min+Garcs[i][n].adj。 path[n]=i。 }//if } //for for(m=0。mGvexnum。m++){ if(final[m]==1amp。amp。m!=w) {printf(\t從%c到%c的最短路徑長度為：%d\t路徑是：,Gvexs[w],Gvexs[m],D[m])。//輸出最大值時(shí)則表示兩點(diǎn)之間沒有最短路徑 Short(G,path,m,w)。 printf(%c,Gvexs[m])。 printf(\n)。 } else printf(\t從%c到%c沒有不存在路徑！\n,Gvexs[w],Gvexs[m])。//判斷是否存在最短路徑 } } main(){ MGrph m。 VertexType ch。 int j。 Creat_YG(amp。m)。 juzhen(amp。m)。 printf(\n請(qǐng)輸入要開始的頂點(diǎn):)。 scanf(%c,amp。ch)。 j=LocateVex(amp。m,ch)。 getchar()。 ShortestPath(amp。m,j)。 getchar()。 }17
范文總結(jié)相關(guān)推薦
鄂ICP備17016276號(hào)-1