華科算法實(shí)驗(yàn)報告-文庫吧
2025-04-28 23:09 本頁面
【正文】 是（i,j）的權(quán)，則在邊（i，j ）不在成本鄰接矩陣時，就被置某個大數(shù)，這里用 N 表示，當(dāng) i=j 時，COST（i,j）被置以 0。3．程序源代碼include include define N 1000void shortestPaths(int v,int *COST,int *DIST,int n)。//最短路徑生成函數(shù)void output2(int *arr,int row,int col)。//輸出成本的鄰接矩陣void outArray1(int *arr,int n)。//輸出更新后其它結(jié)點(diǎn)到起始結(jié)點(diǎn)的路徑長度int main(){ int COST[7][7]={ {0,20,50,30, N, N, N}, {N, 0,25, N, N,70, N}, {N, N, 0,40,25,50, N}, {N, N, N, 0,55, N, N}, {N, N, N, N, 0,10,70}, {N, N, N, N, N, 0,50}, {N, N, N, N, N, N, 0} }。 int DIST[7]。 int v=0。 /* printf(成本鄰接矩陣： \n)。 output2(amp。COST[0][0],7,7)。 */ //生成 0 號結(jié)點(diǎn)到 1 至 6 號結(jié)點(diǎn)的最短路徑 shortestPaths(v,amp。COST[0][0],DIST,7)。 return 0。}void shortestPaths(int v,int *COST,int *DIST,int n){//G 是一個 n 結(jié)點(diǎn)有向圖，它由其成本鄰接矩陣 COST[n][n]表示，DIST[j]被置以結(jié)點(diǎn) v 到 //結(jié)點(diǎn) j 的最短路徑長度，這里 1=j=n。DIST[v]被置成 0 int S[n]。 int pre[n]。//p[w]記錄起始結(jié)點(diǎn)到結(jié)點(diǎn) w 的最短路徑中的 w 前一結(jié)點(diǎn)5 int u,num,i,w。 int tv,td=0。 //初始化：結(jié)點(diǎn) v 以外的結(jié)點(diǎn)未被選中，并更新路徑長度為 v 到其它結(jié)點(diǎn)的初始成本 for(i=0。in。i++) { S[i]=0。 *(DIST+i)=*(COST+v*n+i)。 pre[i]=0。 } S[v]=1。 DIST[v]=0。 //更新路徑長度 for(num=1。numn。num++) { //選擇距離結(jié)點(diǎn) v 最近的結(jié)點(diǎn) w for(w=1。wn。w++) { if(S[w]==0) { td=DIST[w]。 tv=w。 break。 } } for(w++。wn。w++) { if(S[w]==0amp。amp。tdDIST[w]) { td=DIST[w]。 tv=w。 } }
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號-1