工學(xué)最短路徑ppt課件-資料下載頁
2024-11-03 20:39本頁面
【正文】 Vj為第一條最短路徑的終點 所有終點的最短 路徑都已找到 ? 是 否 結(jié)束 開始 以上所有終點中找出路徑長度最短者 （其終點為 Vj） 對于尚未找到最短路徑的每一個終點 Vk， 如果 V0至 Vj的路徑 +邊 (Vj,Vk)構(gòu)成了 V0至 Vk的更短路徑， 則更新 V0至 Vk 的路徑為 V0至 Vj的路徑 +邊 (Vj,Vk) for( i=1。 v。 i++ ) min = INFINITY。 for(k = 0。 k。 ++k) if (final[k]==false) if (D[k]min) { j = k。 min = D[k]。 } final[j] = true。 for(k=0。 k。 ++k) if (final[k]==false amp。amp。 (D[j]+[j][k]D[k])) { D[k] = D[j] + [j][k]。 for(i=0。i。++i) P[k][i] = P[j][i]。 P[k][k] = true。 }//if min = INFINITY。 for(k = 0。 k。 ++k) if (final[k]==false) if (D[k]min) { j = k。 min = D[k]。 } final[j] = true。 西安電子科技大學(xué)軟件學(xué)院 School of Computer Software, Xidian University 17 D[v0] = 0。 final[v0] = true。 //集合 S置初值 for(i=1。 v。 i++) { //求其余終點的最短路徑 min = INFINITY。 for(k=0。 k。 ++k) if (final[k]==false) //頂點 Vk不在集合 S中 if (D[k]min) { j = k。 min = D[k]。 } final[j] = true。 //求出了 V0到 Vj的最短路徑 ， 將 Vj加入集合 S for(k=0。 k。 ++k) if (final[k]==false amp。amp。 (D[j]+[j][k]D[k])) { D[k] = D[j] + [j][k]。 //更新 Vk的路徑長度 for(i=0。i。++i) P[k][i] = P[j][i]。 //更新 Vk的路徑 P[k][k] = true。 //將 Vk加入 V0到 Vk的路徑中 }//if }//for 20 V4 V5 V0 V2 V3 V1 100 10 5 60 10 50 30 迪杰斯特拉算法（ Dijkstra） 缺陷： P[k]記錄了源點至 Vk的路徑上的頂點集合，路徑信息還需要進一步處理。 例如： v0,v4,v3,v5 西安電子科技大學(xué)軟件學(xué)院 School of Computer Software, Xidian University 18 End
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1