弗洛伊德及其算法ppt課件

《弗洛伊德及其算法ppt課件》由會(huì)員分享，可在線閱讀，更多相關(guān)《弗洛伊德及其算法ppt課件（11頁珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

關(guān)于羅伯特 弗洛伊德 RobertW Floyd 1936 2001 計(jì)算機(jī)科學(xué)家 前后斷言法的創(chuàng)始人 堆排序算法和Floyd Warshall算法的創(chuàng)始人之一 1 1978年獲得圖靈獎(jiǎng) 斯坦福大學(xué)計(jì)算機(jī)科學(xué)系教授羅伯特 弗洛伊德是一位 自學(xué)成才的計(jì)算機(jī)科學(xué)家 2 1953年在芝加哥大學(xué)獲得文學(xué)學(xué)士學(xué)位 1958年獲得理學(xué)學(xué)士學(xué)位 1956年他離開西屋電氣公司 到芝加哥的裝甲研究基金會(huì) ArmourResearchFoundation 開始還是當(dāng)操作員 后來就當(dāng)了程序員 3 1965年他應(yīng)聘成為卡內(nèi)基 梅隆大學(xué)的副教授 3年后轉(zhuǎn)至斯坦福大學(xué) 1970年被聘任為教授 1962年他被馬薩諸塞州的ComputerAssociates公司聘為分析員 此時(shí)與Warsall合作發(fā)布Floyed Warshall算法 4 Floyd算法又稱為弗洛伊德算法 插點(diǎn)法 是一種用于尋找給定的加權(quán)圖中頂點(diǎn)間最短路徑的算法 1 Floyd算法介紹 該算法名稱以創(chuàng)始人之一羅伯特 弗洛伊德命名 5 通過一個(gè)圖的權(quán)值矩陣求出它的每兩點(diǎn)間的最短路徑矩陣 2 Floyd算法核心思路 從圖的帶權(quán)鄰接矩陣A a i j n n開始 遞歸地進(jìn)行n次更新 即由矩陣D 0 A 按一個(gè)公式 構(gòu)造出矩陣D 1 又用同樣地公式由D 1 構(gòu)造出D 2 最后又用同樣的公式由D n 1 構(gòu)造出矩陣D n 6 采用的是 松弛技術(shù) 對(duì)在i和j之間的所有其他點(diǎn)進(jìn)行一次松弛 所以時(shí)間復(fù)雜度為O n 3 矩陣D n 的i行j列元素便是i號(hào)頂點(diǎn)到j(luò)號(hào)頂點(diǎn)的最短路徑長度 稱D n 為圖的距離矩陣 同時(shí)還可引入一個(gè)后繼節(jié)點(diǎn)矩陣path來記錄兩點(diǎn)間的最短路徑 2 Floyd算法核心思路 7 1 從任意一條單邊路徑開始 所有兩點(diǎn)之間的距離是邊的權(quán) 如果兩點(diǎn)之間沒有邊相連 則權(quán)為無窮大 3 Floyd算法過程 2 對(duì)于每一對(duì)頂點(diǎn)u和v 看看是否存在一個(gè)頂點(diǎn)w使得從u到w再到v比已知的路徑更短 如果是更新它 比如 要尋找從V5到V1的路徑 根據(jù)D 假如D 5 1 3則說明從V5到V1經(jīng)過V3 路徑為 V5 V3 V1 如果D 5 3 3 說明V5與V3直接相連 如果D 3 1 1 說明V3與V1直接相連 8 把圖用鄰接矩陣G表示出來 如果從Vi到Vj有路可達(dá) 則G i j d d表示該路的長度 否則G i j 無窮大 把各個(gè)頂點(diǎn)插入圖中 比較插點(diǎn)后的距離與原來的距離 G i j min G i j G i k G k j 如果G i j 的值變小 則D i j k 定義一個(gè)矩陣D用來記錄所插入點(diǎn)的信息 D i j 表示從Vi到Vj需要經(jīng)過的點(diǎn) 初始化D i j j 在G中包含有兩點(diǎn)之間最短道路的信息 而在D中則包含了最短通路徑的信息 9 時(shí)間復(fù)雜度 O n 3 4 Floyd算法過程時(shí)間復(fù)雜度與空間復(fù)雜度 空間復(fù)雜度 O n 2 10 Floyd算法適用于APSP AllPairsShortestPaths 是一種動(dòng)態(tài)規(guī)劃算法 稠密圖效果最佳 邊權(quán)可正可負(fù) 此算法簡單有效 由于三重循環(huán)結(jié)構(gòu)緊湊 對(duì)于稠密圖 效率要高于執(zhí)行 V 次Dijkstra算法 5 Floyd算法優(yōu)缺點(diǎn)分析 優(yōu)點(diǎn) 容易理解 可以算出任意兩個(gè)節(jié)點(diǎn)之間的最短距離 代碼編寫簡單 缺點(diǎn) 時(shí)間復(fù)雜度比較高 不適合計(jì)算大量數(shù)據(jù) 11