單源最短路徑的算法及課件設計.ppt

8 3單源最短路徑 給定帶權(quán)有向圖G V E 其中每條邊的權(quán)是非負實數(shù) 另外 還給定V中的一個頂點 稱為源 現(xiàn)在要計算從源到所有其它各頂點的最短路長度 這里路的長度是指路上各邊權(quán)之和 這個問題通常稱為單源最短路徑問題 1 算法基本思想Dijkstra算法是解單源最短路徑問題的貪心算法 8 3單源最短路徑 其基本思想是 設置頂點集合S并不斷地作貪心選擇來擴充這個集合 一個頂點屬于集合S當且僅當從源到該頂點的最短路徑長度已知 初始時 S中僅含有源 設u是G的某一個頂點 把從源到u且中間只經(jīng)過S中頂點的路稱為從源到u的特殊路徑 并用數(shù)組dist記錄當前每個頂點所對應的最短特殊路徑長度 Dijkstra算法每次從V S中取出具有最短特殊路長度的頂點u 將u添加到S中 同時對數(shù)組dist作必要的修改 一旦S包含了所有V中頂點 dist就記錄了從源到所有其它頂點之間的最短路徑長度 8 3單源最短路徑 例如 對右圖中的有向圖 應用Dijkstra算法計算從源頂點1到其它頂點間最短路徑的過程列在下頁的表中 8 3單源最短路徑 Dijkstra算法的迭代過程 初始狀態(tài)下 S中只有一個點 源點v1 s distance path 第二步 將S外距離S最近的點v2加入S 更新相應信息 s distance path 1 60 2 第三步 將S外距離S最近的點v4加入S 更新相應信息 s distance path 1 50 4 90 4 第四步 將S外距離S最近的點v3加入S 更新相應信息 s distance path 1 60 3 第五步 將S外距離S最近的點v5加入S 更新相應信息 s distance path 1 voidDijkstra intG N intv0 intdistance intpath intn 源點v0到其他頂點的最短距離distance和最短路徑下標path int s newint n intminDis i j u 初始化三個數(shù)組 逐次將各點加入S 在當前還未找到最短路徑的頂點集中選取具有最短距離的頂點u 標記頂點u已從集合T加入到集合S中 修改從v0到其他頂點的最短距離和最短路徑 voidDijkstra intG N intv0 intdistance intpath intn 從源點v0到其他頂點的最短距離distance和最短路徑下標path int s newint n intminDis i j u 初始化三個數(shù)組for i 0 i n i distance i G v0 i s i 0 if I v0j if s j 0j if s j 0 G u j MAX distance u G u j distance j distance j distance u G u j path j u 2 算法的正確性和計算復雜性 1 貪心選擇性質(zhì) 2 最優(yōu)子結(jié)構(gòu)性質(zhì) 3 計算復雜性對于具有n個頂點和e條邊的帶權(quán)有向圖 如果用帶權(quán)鄰接矩陣表示這個圖 那么Dijkstra算法的主循環(huán)體需要時間 這個循環(huán)需要執(zhí)行n 1次 所以完成循環(huán)需要時間 算法的其余部分所需要時間不超過 7 5所有點對的最短路徑問題 對于一個各邊權(quán)值均大于0的有n個頂點的帶權(quán)有向圖G V E 求所有頂點之間的最短路徑和最短距離 圖的鄰接矩陣表示法 3 V b a 2 9 6 123 L 029061 0 復習Dijkstra算法 其基本思想是 設置頂點集合S并不斷地作貪心選擇來擴充這個集合 一個頂點屬于集合S當且僅當從源到該頂點的最短路徑長度已知 初始時 S中僅含有源點 設u是G的某一個頂點 把從源點到u且中間只經(jīng)過S中頂點的路稱為從源到u的特殊路徑 并用數(shù)組distance記錄當前每個頂點所對應的最短特殊路徑長度 Dijkstra算法每次從V S中取出具有最短特殊路長度的頂點u 將u添加到S中 同時對數(shù)組distance作必要的修改 一旦S包含了所有V中頂點 distance就記錄了從源到所有其它頂點之間的最短路徑長度 算法中 我們不斷更新以下三個數(shù)組 s數(shù)組 s i 當頂點i加入S時 s i 置1Distance數(shù)組 Distance i 記錄原點到頂點i的最短特殊路徑長度 path數(shù)組 path i 記錄頂點i在其最短特殊路徑上的前驅(qū)頂點 由該數(shù)組可求得原點到各點的最短路徑 如 設源點是頂點1 path數(shù)組如下 例如 對右圖中的有向圖 應用Dijkstra算法計算從源頂點1到其它頂點間最短路徑的過程列在下頁的表中 s distance path 由源點1到頂點5的路徑為 1 4 3 5 方法一 重復調(diào)用Dijkstra算法n次 可輪流以每一個頂點為源點 重復調(diào)用狄克斯特拉算法函數(shù)Dijkstra n次 即可求得所有頂點之間的最短路徑和最短距離 利用Dijkstra 函數(shù)求所有頂點之間的最短路徑算法如下 其中 distance i j 中存放著從頂點i到頂點j的最短距離 path i j 中存放著從頂點i到頂點j的最短路徑的前一頂點下標 voidShortPath AdjMWGraph 由于狄克斯特拉算法的時間復雜度是O n2 所以n次調(diào)用狄克斯特拉算法的時間復雜度是O n3 該問題具有最優(yōu)子結(jié)構(gòu)性質(zhì) 例如上圖中 若路線I和J是A到C的最優(yōu)路徑 則根據(jù)最優(yōu)化原理 路線J必是從B到C的最優(yōu)路線 子問題的構(gòu)造 原問題 每個頂點到其他所有頂點的最短距離最小的子問題D0 從頂點i 不得經(jīng)過任何其他頂點 到頂點j的距離 子問題D1 從頂點i 可以經(jīng)過頂點1 不得經(jīng)過其他任何其他頂點 到頂點j的距離 子問題Dk 從頂點i 可以經(jīng)過頂點1 頂點2 頂點k 不得經(jīng)過任何其他頂點 到頂點j的距離 子問題Dn 從頂點i 可以經(jīng)過頂點1 頂點2 頂點n 到頂點j的距離 即原問題 遞推關系的建立 由di jk 1推出di jk的過程如下若k 0 di jk L i j 因為從i到j不允許經(jīng)過任何其他頂點 若1 k n di jk min di jk 1 di kk 1 dk jk 1 子問題Dk 1 從頂點i 可以經(jīng)過頂點1 頂點2 頂點k 1 到頂點j的距離 子問題Dk 從頂點i 可以經(jīng)過頂點1 頂點2 頂點k 1 頂點k 到頂點j的距離 從子問題Dk 1 到子問題Dk 僅僅多考慮了一個頂點k 我們需要重新考慮從i到j的距離 頂點i到頂點j 是不是從k走會更近 如果從頂點i到頂點j從頂點k走更近 則i到j的距離di jk i到k的距離di kk 1 k到j的距離dk jk 1如果頂點i到頂點j從頂點k走更遠 甚至走不通 則保持原來的距離不變di jk di jk 1 由di jk 1推出di jk的過程 主要考慮的是頂點k的加入會引起什么變化 由不允許路過頂點k到允許路過頂點k 有些點間的距離是否會變的更近 例 考慮下圖所示的帶權(quán)有向圖 求所有頂點之間的最短距離 V b a 123 L 計算過程 Di jk 從頂點i 可以經(jīng)過頂點1 頂點2 頂點k 到頂點j的距離 在D1中 第1行和第一列是不變的 因為說從頂點1到頂點j或頂點j到頂點1 允許經(jīng)過頂點1是沒有意義的 D1 2 3 從頂點2到頂點3的距離 可以經(jīng)過頂點1 1 不經(jīng)過頂點1 仍是D0 2 3 6 2 過頂點1 D0 2 1 D0 1 3 8 9 17取最小值6 D1 3 2 從頂點3到頂點2的距離 可以經(jīng)過頂點1 1 不經(jīng)過頂點1 仍是D0 3 2 2 過頂點1 D0 3 1 D0 1 2 1 2 3取最小值3 D2 1 3 從頂點1到頂點3的距離 也可以經(jīng)過頂點2 1 不經(jīng)過頂點2 仍是D1 1 3 9 2 過頂點2 D1 1 2 D1 2 3 2 6 8取最小值8 算法設計 重要發(fā)現(xiàn) 在從Dk 1到Dk的計算過程中中 第k行和第k列是不變的 因為說從頂點k到頂點j或頂點j到頂點k允許經(jīng)過頂點k是沒有意義的 而在從Dk 1到Dk的計算過程中也只用到第k行和第k列 也就是說 在這一步的計算過程中用到的