工學(xué)最短路徑ppt課件-在線瀏覽
2024-12-21 20:39本頁面
【正文】 ,v2) 10 v3 (v0,v4,v3) 50 v4 (v0,v4) 30 v5 (v0,v4,v3,v5) 60 西安電子科技大學(xué)軟件學(xué)院 School of Computer Software, Xidian University 5 ? Dijkstra算法的基本思想 ? 按路徑長度遞增順序求最短路徑算法 ， 采用鄰接矩陣存儲結(jié)構(gòu) 迪杰斯特拉算法（ Dijkstra） 20 V4 V5 V0 V2 V3 V1 100 10 5 60 10 50 30 ∞ ∞ 10 ∞ 30 100 ∞ ∞ 5 ∞ ∞ ∞ ∞ ∞ ∞ 50 ∞ ∞ ∞ ∞ ∞ ∞ ∞ 10 ∞ ∞ ∞ 20 ∞ 60 ∞ ∞ ∞ ∞ ∞ ∞ 0 1 2 3 4 5 0 1 2 3 4 5 西安電子科技大學(xué)軟件學(xué)院 School of Computer Software, Xidian University 6 1. Dijkstra算法的基本思想 ? 按路徑長度遞增順序求最短路徑算法 。 2. Dijkstra 算法的基本步驟 ? 設(shè) V0是起始源點(diǎn) ， S是 已求得最短路徑的終點(diǎn)集合 。 2) 下一條長度最短的路徑： ① Vi ? V S ， 先求出 V0 到 Vi 中間只經(jīng) S 中頂點(diǎn)的最短路徑； ② 上述路徑中長度最小者即為下一條長度最短的路徑； ③ 將所求最短路徑的終點(diǎn)加入 S 中； 3） 重復(fù) 2） 直到求出所有終點(diǎn)的最短路徑 。 初始時(shí) S ={V0}， D[i]用于保存從源點(diǎn)出發(fā)到達(dá)頂點(diǎn) Vi的最短路徑長度 。 ∞ ∞ 10 ∞ 30 100 ∞ ∞ 5 ∞ ∞ ∞ ∞ ∞ ∞ 50 ∞ ∞ ∞ ∞ ∞ ∞ ∞ 10 ∞ ∞ ∞ 20 ∞ 60 ∞ ∞ ∞ ∞ ∞ ∞ 0 1 2 3 4 5 0 1 2 3 4 5 D[1] = ∞ D[2] = 10 D[3] = ∞ D[4] = 30 D[5] = 100 西安電子科技大學(xué)軟件學(xué)院 School of Computer Software, Xidian University 11 ? 設(shè) V0是源點(diǎn) ， S是已求得最短路徑的終點(diǎn)集合 ， 則 VS是未確定最短路徑的頂點(diǎn)的集合 。 迪杰斯特拉算法（ Dijkstra） ? 初始時(shí) ， 若源點(diǎn)到頂點(diǎn) Vi有邊 ， 則 D[i]為邊上的權(quán)值；否則 ， D[i]為 ∞ 。 迪杰斯特拉算法（ Dijkstra） 2) 求下一條長度最短的路徑： 修改從 V0出發(fā)到達(dá)集合 VU中所有頂點(diǎn) Vk(Vk∈ VS)的路徑的長度 ， 即 如果 D[k] D[j]+arcs[j][k] (Vk∈ VS) ， 則 D[k] = D[j] + arcs[j][k] 上述路徑中長度最小者 （ Vj） 即為下一條長度最短的路徑 ， 同時(shí)將頂點(diǎn)Vj加入 S集合 （ 即將其從集合 VS中去掉 ） ； D[j] = min { D[i] | Vi∈ VS } 3) 重復(fù) 2） 直到
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1