算法12-最短路徑-弗洛伊德(Floyd)算法.ppt

《算法12-最短路徑-弗洛伊德(Floyd)算法.ppt》由會(huì)員分享，可在線閱讀，更多相關(guān)《算法12-最短路徑-弗洛伊德(Floyd)算法.ppt（16頁珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1 1 問題的提出 已知一個(gè)各邊權(quán)值均大于0的帶權(quán)有向圖 對(duì)每一對(duì)頂點(diǎn)vi vj 要求求出vi與vj之間的最短路徑和最短路徑長度 2 解決辦法方法一 每次以一個(gè)頂點(diǎn)為源點(diǎn) 重復(fù)執(zhí)行Dijkstra算法n次 T n O n 方法二 弗洛伊德 Floyd 算法 2 求最短路徑步驟初始時(shí)設(shè)置一個(gè)n階方陣 令其對(duì)角線元素為0 若存在弧 則對(duì)應(yīng)元素為權(quán)值 否則為 逐步試著在原直接路徑中增加中間頂點(diǎn) 若加入中間點(diǎn)后路徑變短 則修改之 否則 維持原值所有頂點(diǎn)試探完畢 算法結(jié)束 3 Floyd算法思想 逐個(gè)頂點(diǎn)試探法 從圖的帶權(quán)鄰接矩陣G arcs出發(fā) 假設(shè)求頂點(diǎn)Vi到Vj的最短路徑 如果從Vi到Vj有弧 則從Vi到Vj存在一條長度為G arcs i j 的路徑 但該路徑是否一定是最短路徑 還需要進(jìn)行n次試探 1 第一次 判別 Vi V0 和 V0 Vj 即判別 Vi V0 Vj 是否存在 若存在 則比較 Vi Vj 和 Vi V0 Vj 的長度 取長度較短的為從Vi到Vj的中間頂點(diǎn)序號(hào)不大于0的最短路徑 2 第二次 再加一個(gè)頂點(diǎn)V1 如果 Vi V1 和 V1 Vj 分別是當(dāng)前找到的中間頂點(diǎn)序號(hào)不大于0的最短路徑 那么 Vi V1 Vj 就有可能是從Vi到Vj的中間頂點(diǎn)序號(hào)不大于1的最短路徑 將它和已經(jīng)得到的從Vi到Vj之間頂點(diǎn)序號(hào)不大于0的最短路徑相比較 取較短者為從Vi到Vj的中間頂點(diǎn)序號(hào)不大于1的最短路徑 3 第三次 再加一個(gè)頂點(diǎn)V2 繼續(xù)進(jìn)行試探 D 1 D 1 為有向網(wǎng)的鄰接矩陣第一步 以D 1 為基礎(chǔ) 以V0為中間頂點(diǎn) 求從Vi到Vj的最短路徑 該路徑或者為從Vi到Vj的邊 或者為 Vi V0 V0 Vj D 0 i j min D 1 i j D 1 i 0 D 1 0 j D 0 i j 為從Vi到Vj的中間頂點(diǎn)序號(hào)不大于0的最短路徑長度 以D 0 為基礎(chǔ) 以V1為中間頂點(diǎn) 求從Vi 到Vj的最短路徑 該路徑或者為從Vi到Vj的邊 或者為從Vi開始通過V0或V1到達(dá)Vj的最短路徑 D 1 i j min D 0 i j D 0 i 1 D 0 1 j 以D 1 為基礎(chǔ) 以V2為中間頂點(diǎn) 求從Vi 到Vj的最短路徑 或者為從Vi到Vj的邊 或者為從Vi開始通過V0 V1 V2到達(dá)Vj的最短路徑 D 2 i j min D 1 i j D 1 i 2 D 1 2 j 以D 2 為基礎(chǔ) 以V3為中間頂點(diǎn) 求從Vi 到Vj的最短路徑 或者為從Vi到Vj的邊 或者為從Vi開始通過V0 V1 V2 V3到達(dá)Vj的最短路徑 D 3 i j min D 2 i j D 2 i 3 D 2 3 j D 3 i j 即為從Vi到Vj的最短路徑長度 9 例題 10 11 4 論點(diǎn) A 1 i j 是從頂點(diǎn)vi到vj 中間頂點(diǎn)是v1的最短路徑的長度 A k i j 是從頂點(diǎn)vi到vj 中間頂點(diǎn)的序號(hào)不大于k的最短路徑的長度 A n 1 i j 是從頂點(diǎn)vi到vj的最短路徑長度 證明 歸納證明 始?xì)w納于s 上角標(biāo) 1 歸納基礎(chǔ) 當(dāng)s 1時(shí) A 1 i j Edge i j vi到vj 不經(jīng)過任何頂點(diǎn)的邊 是最短路徑 2 歸納假設(shè) 當(dāng)s k時(shí) A s i j 是從頂點(diǎn)vi到vj 中間頂點(diǎn)的序號(hào)不大于s的最短路徑的長度 3 當(dāng)s k時(shí) 12 i j k A k 1 i k A k 1 k j A k 1 i j 因?yàn)?A k i j min A k 1 i j A k 1 i k A k 1 k j 由歸納假設(shè)知 A k 1 i j 是i到j(luò)的最短路徑 標(biāo)號(hào)不高于k 1 A k 1 i k 是i到k的最短路徑 標(biāo)號(hào)不高于k 1 A k 1 k j 是k到j(luò)的最短路徑 標(biāo)號(hào)不高于k 1 所以 A k i j 是i到j(luò)的最短路徑 標(biāo)號(hào)不高于k 13 圖用鄰接矩陣存儲(chǔ)edge 存放最短路徑長度path i j 是從Vi到Vj的最短路徑上Vj前一頂點(diǎn)序號(hào) 5 算法實(shí)現(xiàn) voidfloyd for inti 0 i n i 矩陣dist與path初始化for intj 0 j n j 置A 1 dist i j Edge i j path i j 1 初始不經(jīng)過任何頂點(diǎn)for intk 0 k n k 產(chǎn)生dist k 及path k for i 0 i n i for j 0 j n j if dist i k dist k j dist i j dist i j dist i k dist k j path i j k 縮短路徑 繞過k到j(luò) floyd 14 6 算法分析 設(shè)最內(nèi)層循環(huán)體為基本操作 算法有三層循環(huán) 每層循環(huán)n次 所以T n O n3 15 16 以Path 3 為例 對(duì)最短路徑的讀法加以說明 從A 3 知 頂點(diǎn)1到0的最短路徑長度為a 1 0 11 其最短路徑看path 1 0 2 path 1 2 3 path 1 3 1 表示頂點(diǎn)0 頂點(diǎn)2 頂點(diǎn)3 頂點(diǎn)1 從頂點(diǎn)1到頂點(diǎn)0最短路徑為