圖的最短路徑算法-Floyd算法-弗洛伊德算法

2021-01-11 騰訊網

Floyd算法又稱為插點法，是一種利用動態規劃的思想尋找給定的加權圖中多源點之間最短路徑的算法

在計算機科學中，Floyd-Warshall算法是一種在具有正或負邊緣權重（但沒有負周期）的加權圖中找到最短路徑的算法。算法的單個執行將找到所有頂點對之間的最短路徑的長度（加權）。 雖然它不返迴路徑本身的細節，但是可以通過對算法的簡單修改來重建路徑。 該算法的版本也可用於查找關係R的傳遞閉包，或（與Schulze投票系統相關）在加權圖中所有頂點對之間的最寬路徑。

Floyd-Warshall算法是動態規劃的一個例子，並在1962年由Robert Floyd以其當前公認的形式出版。然而，它基本上與Bernard Roy在1959年先前發表的算法和1962年的Stephen Warshall中找到圖形的傳遞閉包基本相同，並且與Kleene的算法密切相關 在1956年）用於將確定性有限自動機轉換為正則表達式。算法作為三個嵌套for循環的現代公式首先由Peter Ingerman在1962年描述。

該算法也稱為Floyd算法，Roy-Warshall算法，Roy-Floyd算法或WFI算法。

優缺點：

Floyd算法適用於APSP(AllPairsShortestPaths)，是一種動態規划算法，稠密圖效果最佳，邊權可正可負。此算法簡單有效，由於三重循環結構緊湊，對於稠密圖，效率要高於執行|V|次Dijkstra算法。

優點：容易理解，可以算出任意兩個節點之間的最短距離，代碼編寫簡單

缺點：時間複雜度比較高，不適合計算大量數據。

時間複雜度:O(n^3)；空間複雜度:O(n^2)；

任意節點i到j的最短路徑兩種可能：

直接從i到j；

從i經過若干個節點k到j。

map（i，j）表示節點i到j最短路徑的距離，對於每一個節點k，檢查map（i，k）+map（k，j）小於map(i，j),如果成立，map（i，j） = map（i，k）+map（k，j）；遍歷每個k，每次更新的是除第k行和第k列的數。

Floyd 第一迭代

Floyd 第二迭代

Floyd 第三迭代

大家試試能不能做出來下面的這道題：

相關焦點

  • 短小精悍的多源最短路徑算法—Floyd算法
    在圖論中，在尋路最短路徑中除了Dijkstra算法以外，還有Floyd算法也是非常經典，然而兩種算法還是有區別的，Floyd主要計算多源最短路徑。在單源正權值最短路徑，我們會用Dijkstra算法來求最短路徑，並且算法的思想很簡單——貪心算法:每次確定最短路徑的一個點然後維護(更新)這個點周圍點的距離加入預選隊列，等待下一次的拋出確定。但是雖然思想很簡單，實現起來是非常複雜的，我們需要鄰接矩陣(表)儲存長度，需要優先隊列(或者每次都比較)維護一個預選點的集合。
  • 自動駕駛想要更安全 路徑規划算法很重要
    智能車的自動駕駛行為即是將車從起始位姿「搬運」到目標位姿，車輛的運動限制在路面上、同時其運動學及動力學模型使得其不能像空中的無人機一樣隨意調整航向角，因此，規劃的路徑除了考慮路程最短、無碰撞外還需要考慮車輛運動軌跡的可執行性。| 車輛路徑規划算法根據車輛導航系統的研究歷程, 車輛路徑規划算法可分為靜態路徑規划算法和動態路徑算法。
  • 算法丨狄克斯特拉算法示例
    這個圖中的節點是大家願意拿出來交換的東西，邊的權重是交換時需要額外加多少錢。拿海報換吉他需要額外加30美元，拿黑膠唱片換吉他需要額外加15美元。Rama需要確定採用哪種路徑樂譜換成鋼琴需要支付的額外費用最少。
  • 你不得不看的最重要的算法類型
    算法： 算法是解決問題的分步過程。一個好的算法應該在時間和空間上進行優化。不同類型的問題需要以最優化的方式解決不同類型的算法技術。世界上有很多類型的算法，但是本文將討論您必須知道的最重要和最基本的算法。
  • 圖像處理算法有哪些_圖像處理十大經典算法
    }}二、廣度優先搜索此圖遍歷中最基本的倆種算法，BFS，DFS，入選本圖算法十大算法，自是無可爭議。因為，這倆種搜索算法，應用實為廣泛而重要。A*算法，作為啟發式算法中很重要的一種，被廣泛應用在最優路徑求解和一些策略設計的問題中。
  • 漫畫:數據結構之最短路徑 Dijkstra 算法的優化
    圖的 「最短路徑」 問題》一文中小灰介紹了單源最短路徑算法 Dijkstra。距離表的Key是頂點名稱，Value是從起點A到對應頂點的已知最短距離，默認為無窮大；前置頂點表的Key是頂點名稱，Value是從起點A到對應頂點的已知最短路徑的前置定點。
  • 從算法上解讀自動駕駛是如何實現的?
    智能車的自動駕駛行為即是將車從起始位姿「搬運」到目標位姿，車輛的運動限制在路面上、同時其運動學及動力學模型使得其不能像空中的無人機一樣隨意調整航向角，因此，規劃的路徑除了考慮路程最短、無碰撞外還需要考慮車輛運動軌跡的可執行性。
  • 這可能是史上最全的Python算法集!
    藍線是實際路徑。黑線是導航推測路徑。紅線是基於圖的SLAM估算的路徑。黑星是地標，用於生成圖的邊。相關閱讀：用動態窗口方式避免碰撞https://www.ri.cmu.edu/pub_files/pub1/fox_dieter_1997_1/fox_dieter_1997_1.pdf6.2 基於網格的搜索這是利用迪傑斯特拉（Dijkstra）算法實現的基於二維網格的最短路徑規劃
  • 程式設計師必須掌握的核心算法有哪些?
    2、棧與隊列棧（必學）隊列（必學）優先隊列、堆（必學）多級反饋隊列（原理與應用）特別是優先隊列，再刷題的時候，還是經常用到的，隊列與棧，是最基本的數據結構，必學。可以通過博客來學習。推薦書籍是《算法第四版》，這本書講的很詳細，而且配了很多圖演示，還是挺好懂的。
  • 推薦 :這可能是史上最全的 Python 算法集
    基於圖的SLAM這是基於圖的SLAM的示例。藍線是實際路徑。黑線是導航推測路徑。紅線是基於圖的SLAM估算的路徑。黑星是地標，用於生成圖的邊。基於網格的搜索2.1 迪傑斯特拉算法這是利用迪傑斯特拉（Dijkstra）算法實現的基於二維網格的最短路徑規劃。
  • 圖注意力網絡一作:圖表徵學習在算法推理領域的研究進展
    Veličković 試圖為我們解答：神經網絡能否像常規算法一樣穩健地推理？本次演講分為四個部分：圖神經網絡基準測試、強泛化能力、多任務學習和算法探索。圖神經網絡基準測試第一部分主要討論的是，Cora 和 Cite 這類 GNN 基準測試數據集的不足，以及使用神經網絡模擬算法推理的優勢。
  • 《漫畫算法2》2021全新進階版來襲!安排!
    2.《漫畫算法》在雙十一期間登上了公交站的廣告牌第三章 圖介紹圖這種數據結構，以及深度優先遍歷、廣度優先遍歷、單源最短路徑、多源最短路徑算法。第四章 查找介紹「查找」相關的算法和數據結構，包括二分查找算法、RK算法、KMP算法、跳表。
  • 主宰全球的10大算法
    Leiserson 《算法導論第3版》)可以這樣理解，算法是用來解決特定問題的一系列步驟（不僅計算機需要算法，我們在日常生活中也在使用算法）。算法必須具備如下3個重要特性：有窮性，執行有限步驟後，算法必須中止。確切性，算法的每個步驟都必須確切定義。
  • 長URL連結轉短連結算法
    開始以為短連結是按照某種算法把原始連結壓縮為短連結，再根據算法從短連結反算成原始連結的。後來嘗試了下壓縮算法（比如gzip 壓縮算法），發現對於url 這種字符串越是壓縮，長度就越長。通過對壓縮算法的一些了解，發現靠壓縮算法來實現這個功能不太靠譜。
  • 2020 圖算法工程師面試基礎、要點
    這段時間面試連連，幾輪下來的感受就是，好點兒的公司對細節摳的很細，希望求職者能夠對使用的算法以及這個算法的其它觸類旁通的領域都能夠有系統的理解。 本文參照之前的：我們如何通過圖算法來幫助提高機器學習算法的性能？以及【圖算法：概覽（https://zhuanlan.zhihu.com/p/64984300）】以及之前劉教授出的GNN系統介紹的書的基礎知識部分進行總結。 圖是一種數據結構，它對一組對象（節點)及其關係(邊)進行建模。
  • SEO算法:巴郎深談石榴算法與算法對策
    前言每一套SEO算法的出臺都是在提升用戶體驗，石榴算法就是重點針對低質量廣告頁面而誕生的-SEO算法目錄( 4867 字)01.上線時間與宗旨02.石榴算法的意義03.石榴算法的誕生04.SEO從業人員如何應對石榴算法最後的話01
  • 詳解JAVA數據結構與算法:排序算法
    2) 事前估 算的方 法 通過分析某個算法的 時間複雜度 來判斷哪個算法更優 .時間頻度時間頻度：一個算法花費的時間與算法中語句的執行次數成正比例，哪個算法中語句執行次數多，它花費時間就多。一個算法中的語句執行次數稱為語句頻度或時間頻度。記為T(n)。
  • 算法的入門丨最基礎的排序算法,選擇、冒泡、插入
    大家在學習java的過程中一定都會接觸到排序算法，而且排序算法是編程學習的過程中最先接觸的算法。今天給大家帶來算法的一次回憶，排序算法入門的三種基礎算法——選擇排序、冒牌排序和插入排序。選擇排序選擇排序，弟中弟，最沒用的算法，時間複雜度非常之高，所以說這個算法是最沒用的算法。但是這個算法是給編程學習者帶來思路的，用來做算法入門的墊腳石是非常不錯的。排序算法的思路：過濾整個數組，將最小的數換到第一位，重複該過程，直到遍歷數組，結束程序。首先，寫一個循環遍歷數組並將數組中元素列印出來的方法。命名為print( ); 方法。
  • 案例實踐丨最優化算法的前世今生
    那麼所謂最優化問題，就是指用最優的方式去平衡理想與現實之間的關係。以簡單的郵差送信問題為例，郵差從A出發，送信到BCD，最後回到A。郵差每天必須經過BCD，而且每個點每天只能經過一次，在這樣的約束條件下，他的目標函數是儘可能以最短的時間完成送信。這個問題非常簡單，只要把所有的路徑枚舉出來，然後取最短時間的方式即可。
  • 人像形變算法簡介及應用
    圖2：不同變換關係圖，引用自[3]2.2 移動最小二乘形變算法移動最小二乘算法[1](Moving Least Squares，簡稱MLS)是由Scott Schaefer等在2006年提出的一種圖像形變算法，由於該方法能產生自然、平滑的圖像形變效果，因此在圖像形變中得到了廣泛使用。