工學(xué)最短路徑ppt課件-閱讀頁
2024-11-18 20:39本頁面
【正文】 求出所有頂點(diǎn)的最短路徑 。v。 D[v] = [v0][v]。w。 if (D[v]INFINITY) { P[v][v0] = true。 }//if }//for 20 V4 V5 V0 V2 V3 V1 100 10 5 60 10 50 30 迪杰斯特拉算法（ Dijkstra） 西安電子科技大學(xué)軟件學(xué)院 School of Computer Software, Xidian University 14 D[V0] = 0。 //集合 S置初值 for(i=1。 i++) { //求其余頂點(diǎn)的最短路徑 min = INFINITY。 k。 min = D[k]。 //頂點(diǎn) Vj加入集合 S //根據(jù)需要更新其余終點(diǎn)的路徑； }//for 20 V4 V5 V0 V2 V3 V1 100 10 5 60 10 50 30 迪杰斯特拉算法（ Dijkstra） 西安電子科技大學(xué)軟件學(xué)院 School of Computer Software, Xidian University 15 D[v0] = 0。 //集合 S置初值 for(i=1。 i++) { //求其余終點(diǎn)的最短路徑 min = INFINITY。 k。 min = D[k]。 //求出了 V0到 Vj的最短路徑 ， 將 Vj加入集合 S for(k=0。 ++k) //更新其余頂點(diǎn)的路徑及長度 if (final[k]==false amp。 (D[j]+[j][k]D[k])) { D[k] = D[j] + [j][k]。i。 //更新 Vk的路徑 P[k][k] = true。 v。 for(k = 0。 ++k) if (final[k]==false) if (D[k]min) { j = k。 } final[j] = true。 k。amp。 for(i=0。++i) P[k][i] = P[j][i]。 }//if min = INFINITY。 k。 min = D[k]。 西安電子科技大學(xué)軟件學(xué)院 School of Computer Software, Xidian University 17 D[v0] = 0。 //集合 S置初值 for(i=1。 i++) { //求其余終點(diǎn)的最短路徑 min = INFINITY。 k。 min = D[k]。 //求出了 V0到 Vj的最短路徑 ， 將 Vj加入集合 S for(k=0。 ++k) if (final[k]==false amp。 (D[j]+[j][k]D[k])) { D[k] = D[j] + [j][k]。i。 //更新 Vk的路徑 P[k][k] = true。 例如： v0,v4,v3,v5 西安電子科技大學(xué)軟件學(xué)院 School of Computer Software, Xidian University 18 End
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1