數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告--dijkstra算法求最短路徑-wenkub
2023-04-26 22:48:13 本頁(yè)面
【正文】 Vj加入到S中。 程序流程圖：(1) 輸入頂點(diǎn)個(gè)數(shù)n，邊的條數(shù)，初始化鄰接矩陣。 //頂點(diǎn)關(guān)系類型typedef int InfoType。 typedef struct{ VertexType vexs[MAX_VERTEX_NUM]。 //鄰接矩陣表示的圖 char VertexType。 for(b=0。 }//if return(j)。 int w=1。Garum)。i++) { printf(請(qǐng)輸入圖的第%d個(gè)頂點(diǎn):,w)。Gvexs[i])。i++) for(j=0。 } for(k=0。 scanf(%c,%c,%d,amp。 printf(\n)。//邊v1,v2的權(quán)值賦為1，如需要權(quán)值操作則相應(yīng)修改一下即可 Garcs[i][j].info=NULL。 printf(\t)。 for(j=0。 for(k=0。 //無(wú)權(quán)值的直接輸出最大值 } }在圖的鄰接矩陣顯示中，分別利用for循環(huán)輸出了矩陣的行列標(biāo)，使矩陣很明了。 for(i=0。jGvexnum。kGvexnum。 k=path[i]。頂點(diǎn)間無(wú)邊時(shí)其對(duì)應(yīng)權(quán)值用無(wú)窮大表示。 dist[i]=cost[v0][i] 初始化求到每個(gè)頂點(diǎn)的最短路徑時(shí)都經(jīng)過v0頂點(diǎn)。 s[i]=0。同時(shí)V0到Vi的最短路徑中經(jīng)過的頂點(diǎn)數(shù)加1，即path[i].num++。3) 在程序的調(diào)試過程可暫時(shí)多加一些輸出語(yǔ)句以便及時(shí)查看一下中間運(yùn)行情況，并對(duì)程序規(guī)格說明作調(diào)整和改動(dòng)。因?yàn)樵诙x結(jié)點(diǎn)時(shí)，使用的是結(jié)構(gòu)體數(shù)組，所以當(dāng)處理V0到每個(gè)結(jié)點(diǎn)的最短路徑時(shí)，導(dǎo)致無(wú)法具體記錄經(jīng)過的頂點(diǎn)數(shù)，只能記錄源點(diǎn)、終點(diǎn)前一頂點(diǎn)以及終點(diǎn)。第6章 學(xué)習(xí)心得體會(huì) 通過對(duì)本次課程設(shè)計(jì)的學(xué)習(xí)與交流，使我學(xué)習(xí)到一部分很重要的關(guān)于編程方面思想，同時(shí)也獲得了部分學(xué)習(xí)其他學(xué)科的方法。通過對(duì)本次課程設(shè)計(jì)涉及的問題的分析和處理，了解到學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)對(duì)編程的技巧和思想方法。 //頂點(diǎn)關(guān)系類型typedef int InfoType。 typedef struct{ VertexType vexs[MAX_VERTEX_NUM]。 //鄰接矩陣表示的圖/* 確定位置函數(shù) */int LocateVex(MGrph *G,VertexType v){ int j,b。 break。 int w=1。Garum)。i++) { printf(請(qǐng)輸入圖的第%d個(gè)頂點(diǎn):,w)。Gvexs[i])。i++) for(j=0。 } for(k=0。 scanf(%c,%c,%d,amp。 printf(\n)。//邊v1,v2的權(quán)值賦為1，如需要權(quán)值操作則相應(yīng)修改一下即可 Garcs[i][j].info=NULL。 printf(\t)。 for(j=0。 for(k=0。 //無(wú)權(quán)值的直接輸出最大值 } }}void Short(MGrph *G,int path[],int i,int w){ //遞歸函數(shù)是用來(lái)輸出從源點(diǎn)出發(fā)到終點(diǎn)之前的頂點(diǎn) //思想是patn[]數(shù)組來(lái)表示前驅(qū)頂點(diǎn)的位置，然后遞歸輸出每個(gè)頂點(diǎn)的前驅(qū) int k。//輸出k位置的頂點(diǎn)值 }void ShortestPath(MGrph *G,int w){ //Dijkstrs算法應(yīng)用 int i,k,m,n,min。i++) { path[i]=w。final[w]=1。m++) { min=INFINITY。 min=D[k]。n++) if(!final[n]amp。 }//if } //for for(m=0。m!=w) {printf(\t從%c到%c的最短路徑長(zhǎng)度為：%d\t路徑是：,Gvexs[w],Gvexs[m],D[m])。 } else printf(\t從%c到%c沒有不存在路徑！\n,Gvexs[w],Gvexs[m])。 Creat_YG(amp。 printf(\n請(qǐng)輸入要開始的頂點(diǎn):)。m,ch)。 getchar()。 ShortestPath(amp。ch)。 juzhen(amp。 VertexType ch。 printf(%c,Gvexs[m])。m++){ if(final[m]==1amp。(min+Garcs[i][n].adj)D[n]) { D[n]=min+Garcs[i][n].adj。 for(n=0。kGvexnum。//源點(diǎn)位置的D[w]為0，final[w]=1標(biāo)記已經(jīng)入集合，path[w]=100，表示該前驅(qū)為100 for(m=1。//這是一個(gè)標(biāo)記數(shù)組，一開始所有頂點(diǎn)位置對(duì)應(yīng)的數(shù)組值全部標(biāo)記為0 D[i]=Garcs[w][i].adj。 //定義三個(gè)數(shù)組，final[]標(biāo)記該頂點(diǎn)是否在最短路徑上 //path[]用來(lái)記錄頂點(diǎn)的前驅(qū)頂點(diǎn)的位置，D[]是用來(lái)記錄從源點(diǎn)到該點(diǎn)的最短路徑長(zhǎng)度 for(i=0。 if(k!=w) Short(G,path,k,w )。k++) { if(Garcs[
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1