數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)—城市道路交通咨詢系統(tǒng)-資料下載頁(yè)
2025-06-25 07:23本頁(yè)面
【正文】 !S[w] amp。amp。 D2[w]min) { v=w。min=D2[w]。 }//w頂點(diǎn)離v1頂點(diǎn)更近 S[v]=TRUE。 for(w=1。w=n。w++)//更新當(dāng)前最短路徑及距離 if(!S[w]amp。amp。(D2[v]+Garcs[v][w]D2[w])) { D2[w]=D2[v]+Garcs[v][w]。 P2[w]=v。 } } printf( === 路徑長(zhǎng)度，路徑 ===\n)。 for(i=1。i=n。i++) { printf( === %5d,D2[i])。 printf(%5d,i)。 v=P2[i]。 while(v!=0) {printf(%d,v)。 v=P2[v]。} printf(\n)。 } } /*費(fèi)洛伊德算法*/ void Floyd(MGraph *G,int n) {//利用費(fèi)洛伊德算法，求出最短路徑 int i,j,k。 for(i=1。i=n。i++) for(j=1。j=n。j++) { if(Garcs[i][j]!=Maxint) P[i][j]=j。 else P[i][j]=0。 D[i][j]=Garcs[i][j]。 } for(k=1。k=n。k++) { for(i=1。i=n。i++) for(j=1。j=n。j++) { if(D[i][k]+D[k][j]D[i][j]) { D[i][j]=D[i][k]+D[k][j]。 P[i][j]=P[i][k]。 } } } } void main() { printf( ***********歡迎使用城市交通咨詢系統(tǒng)**********\n)。 printf(\n)。 printf( =============================================\n)。MGraph *G。 int n,e,v,w,k。 int xz=1。 G=(MGraph *)malloc(sizeof(MGraph))。 printf( === 輸入城市個(gè)數(shù)和路徑個(gè)數(shù)n，e： )。 scanf(%d,%d,amp。n,amp。e)。 CreateMGraph(G,n,e)。//建立圖的存儲(chǔ)結(jié)構(gòu) while(xz!=0) { printf( **************求城市之間的最短距離*************\n)。 printf( ===============================================\n)。 printf( ===============\n)。 printf( ===============\n)。 printf( ===============================================\n)。printf(\n)。printf(\n)。printf( ======請(qǐng)選擇：1或2，選擇0 退出： )。 scanf( %d,amp。xz)。if(xz==2) { Floyd(G,n)。////調(diào)用費(fèi)洛伊德算法 printf( =============================================\n)。printf( =======輸入源點(diǎn)和終點(diǎn)：v，w： )。 scanf(%d,%d,amp。v,amp。w)。 k=P[v][w]。 if(k==0) printf( =====頂點(diǎn) %d 到 %d 無(wú)路徑！==================\n,v,w)。 else { printf( =====從頂點(diǎn) %d 到 %d 最短路徑是 %d ,v,w,v)。 while(k!=w) { printf(%d,k)。 k=P[k][w]。//k為v的后繼頂點(diǎn) } printf(%d\n,k)。//輸出后繼頂點(diǎn) printf( ======路徑長(zhǎng)度：%d ===\n,D[v][w])。 } } else if(xz==1) { printf( ===============求單源路徑，輸入源點(diǎn)v: )。 scanf(%d,amp。v)。 Dijkstra(G,v,n)。//調(diào)用迪杰斯特拉算法 } } printf( ***************結(jié)束求最短路徑，再見*****************\n)。 }19
公司管理相關(guān)推薦
鄂ICP備17016276號(hào)-1