在圖論中，在尋路最短路徑中除了<code>Dijkstra</code>算法以外，還有<code>Floyd</code>算法也是非常經典，然而兩種算法還是有差別的，<code>Floyd</code>主要計算多源最短路徑。
在單源正權值最短路徑，我們會用<code>Dijkstra</code>算法來求最短路徑，并且算法的思想很簡單—貪心算法:每次确定最短路徑的一個點然後維護(更新)這個點周圍點的距離加入預選隊列，等待下一次的抛出确定。雖然思想很簡單，實作起來是非常複雜的，我們需要鄰接矩陣(表)儲存長度，需要優先隊列(或者每次都比較)維護一個預選點的集合。還要用一個boolean數組标記是否已經确定、還要……
總之，<code>Dijkstra</code>算法的思想上是很容易接受的，但是實作上其實是非常麻煩的。但是單源最短路徑解算暫時還沒有有效的辦法，複雜度也為<code>O(n2)</code>。
而在n點圖中想求多源最短路徑,如果從Dijkstra算法的角度上，需要将<code>Dijkstra</code>執行n次才能獲得所有點之間的最短路徑，不過執行n次Dijkstra算法即可,複雜度為<code>O(n3)</code>。但是這樣感覺很臃腫，代碼量巨大，占用很多空間記憶體。有沒有啥方法能夠稍微變變口味呢？
答案是有的，今天就帶大家一起了解一下牛逼轟轟的Floyed算法。
什麼是Floyed算法？
Floyd算法又稱為插點法，是一種利用動态規劃的思想尋找給定的權重圖中多源點之間最短路徑的算法，與Dijkstra算法類似。該算法名稱以創始人之一、1978年圖靈獎獲得者、斯坦福大學計算機科學系教授羅伯特·弗洛伊德命名。
簡單的來說，算法的主要思想是動态規劃(dp)，而求最短路徑需要不斷松弛(熟悉spfa算法的可能熟悉松弛)。
而算法的具體思想為：
1 .鄰接矩陣(二維數組)<code>dist</code>儲存路徑，數組中的值開始表示點點之間初始直接路徑，最終是點點之間的最小路徑，有兩點需要注意的，第一是如果沒有直接相連的兩點那麼預設為一個很大的值(不要因為計算溢出成負數)，第二是自己和自己的距離要為0。
2 .從第1個到第n個點依次加入松弛計算，每個點加入進行試探枚舉是否有路徑長度被更改(自己能否更新路徑)。順序加入(k枚舉)松弛的點時候，需要周遊圖中每一個點對(i,j雙重循環)，判斷每一個點對距離是否因為加入的點而發生最小距離變化，如果發生改變(變小)，那麼兩點(i,j)距離就更改。
2 .重複上述直到最後插點試探完成。
其中第2步的狀态轉移方程為:
其中<code>dp[a][b]</code>的意思可以了解為點a到點b的最短路徑,是以<code>dp[i][k]</code>的意思可以了解為i到k的最短路徑<code>dp[k][j]</code>的意思為k到j的最短路徑.
咱們圖解一個案例，初始情況每個點隻知道和自己直接相連的點的距離，而其他間接相連的點還不知道距離，比如A-B=2,A-C=3但是B-C在不經過計算的情況是不知道長度的。
加入第一個節點<code>A</code>進行更新計算,大家可以發現，由于A的加入，使得本來不連通的<code>B，C</code>點對和<code>B，D</code>點對變得聯通，并且加入A後距離為目前最小,同時你可以發現加入<code>A</code>其中也使得<code>C-D</code>多一條聯通路徑（6+3），但是<code>C-D</code>聯通的話距離為9遠遠大于本來的<code>(C,D)</code>聯通路徑2，是以這條不進行更新。
咱們繼續加入第二個節點<code>B</code>，這個點執行和前面<code>A</code>相同操作進行。對一些點進行更新。因為和B相連的點比較多，可以産生很多新的路徑，這裡給大家列舉一下并做一個說明,這裡新路徑我統一用1表示，原來長度用0表示。
AF1=AB+BF=6+2=8 < AF0(∞) 進行更新
AE1=AB+BE=2+4=6 < AE0(∞) 進行更新
CE1=CB+BE=5+5=9 < CE0(∞) 進行更新
CF1=CB+BF=5+6=11<CF0(∞) 進行更新
EF1=EB+BF=4+6=10<EF0(∞) 進行更新
當然，也有一些新的路徑大于已有路徑不進行更新，例如：
AC1=AB+BC=2+5=7>AC0(3) 不更新
AD1=AB+BD=2+8=10>AD0(6) 不更新
……
更多路徑這裡就不一一列舉了。
後序加入C、D、E、F都是進行相同的操作,最終全部加完沒有路徑可以更新就結束停止。實際上這個時候圖中的連線就比較多了。這些連線都是代表目前的最短路徑。 這也和我們的需求貼合，我們最終要的是所有節點的最短路徑。每個節點最終都應該有5條指向不同節點的邊！ 矩陣對應邊值就是點點之間最短路徑。
至于算法的模拟兩部核心已經告訴大家了，大家可以自行模拟剩下的。
而對于程式而言，這個插入的過程相當簡單。核心代碼隻有四行！ 這個寫法适合有向圖和無向圖，無向圖的算法優化後面會說。
代碼如下
執行結果為：
可以自行計算，圖和上篇的Dijkstra用的圖是一緻的，大家可以自行比對，結果一緻，說明咱麼的結果成功的。
當然，在你學習的過程中，可以在每加入一個節點插入完成後，列印鄰接矩陣的結果，看看前兩部和筆者的是否相同(有助于了解)，如果相同，則說明正确！
對于加入點更新你可能還是有點疑惑其中的過程，那咱麼就用一個局部來示範一下幫助你進一步了解Floyd算法，看其中AB最短距離變化情況祝你了解：
自己會沒會？刷一道題就可以知道了，剛好力扣1334是一道Floyd算法解決的問題。
題目描述為：
有 n 個城市，按從 0 到 n-1 編号。給你一個邊數組 edges，其中 edges[i] = [fromi, toi, weighti] 代表 fromi 和 toi 兩個城市之間的雙向權重邊，距離門檻值是一個整數 distanceThreshold。
傳回能通過某些路徑到達其他城市數目最少、且路徑距離 最大 為 distanceThreshold 的城市。如果有多個這樣的城市，則傳回編号最大的城市。
注意，連接配接城市 i 和 j 的路徑的距離等于沿該路徑的所有邊的權重之和。
示例1：
輸入：n = 4, edges = [[0,1,3],[1,2,1],[1,3,4],[2,3,1]], distanceThreshold = 4 輸出：3 解釋：城市分布圖如上。 每個城市門檻值距離 distanceThreshold = 4 内的鄰居城市分别是： 城市 0 -> [城市 1, 城市 2] 城市 1 -> [城市 0, 城市 2, 城市 3] 城市 2 -> [城市 0, 城市 1, 城市 3] 城市 3 -> [城市 1, 城市 2] 城市 0 和 3 在門檻值距離 4 以内都有 2 個鄰居城市，但是我們必須傳回城市 3，因為它的編号最大。
示例2：
輸入：n = 5, edges = [[0,1,2],[0,4,8],[1,2,3],[1,4,2],[2,3,1],[3,4,1]], distanceThreshold = 2 輸出：0 每個城市門檻值距離 distanceThreshold = 2 内的鄰居城市分别是： 城市 0 -> [城市 1] 城市 1 -> [城市 0, 城市 4] 城市 2 -> [城市 3, 城市 4] 城市 3 -> [城市 2, 城市 4] 城市 4 -> [城市 1, 城市 2, 城市 3] 城市 0 在門檻值距離 2 以内隻有 1 個鄰居城市。
提示：
2 <= n <= 100 1 <= edges.length <= n * (n - 1) / 2 edges[i].length == 3 0 <= fromi < toi < n 1 <= weighti, distanceThreshold <= 10^4 所有 (fromi, toi) 都是不同的。
思路分析：
拿到一道題，首先就是要了解題意，而這道題的意思借助案例也是非常能夠了解，其實就是判斷在distanceThreshold範圍内找到能夠到達的最少點的編号，如果多個取最大即可。正常求到達最多情景比較多這裡求的是最少的，但是思路都是一樣的。
這道題如果使用搜尋，那複雜度就太高了啊，很明顯要使用多源最短路徑Floyd算法，具體思路為;
1 .先使用Floyd算法求出點點之間的最短距離，時間複雜度O(n3)
2 . 統計每個點與其他點距離在distanceThreshold之内的點數量，統計的同時看看是不是小于等于已知最少個數的，如果是，那麼儲存更新。
3 .傳回最終的結果。
實作代碼：
那麼想一下優化空間：Floyd算法還有優化空間嘛？
有的，這個是個無向圖，也就是加入點的時候枚舉其實會有一個重複的操作過程(例如枚舉AC和CA是效果一緻的)，是以我們在Floyd算法的實作過程中過濾掉重複的操作，具體代碼為：
對于<code>Floyd</code>算法，如果初次接觸不一定能夠了解這個松弛的過程。
<code>Floyd</code>像什麼呢，最終最短路徑大部分都是通過計算得到而存儲下來直接使用的，我覺得它和MySQL視圖有點像的，視圖是一個虛表在實表上計算獲得的，但是計算之後各個資料就可以直接使用，<code>Floyd</code>是在原本的路徑圖中通過一個動态規劃的政策計算出來點點之間的最短路徑。
<code>Floyd</code>和<code>Dijkstra</code>是經典的最短路徑算法，兩者有相似也有不同。在複雜度上，<code>Dijkstra</code>算法時間複雜度是<code>O(n2)</code>,<code>Floyd</code>算法時間複雜度是<code>O(n3)</code>；在功能上，Dijkstra是求單源最短路徑，并且路徑權值不能為負，而<code>Floyd</code>是求多源最短路徑，可以有負權值；算法實作上，Dijkstra 是一種貪心算法實作起來較複雜，<code>Floyd</code>基于動态規劃實作簡單；兩個作者<code>Dijkstra</code>和<code>Floyd</code>都是牛逼轟轟的大人物，都是圖靈獎的獲得者。
除了<code>Floyd</code>算法，堆排序算法<code>heapSort</code>也是<code>Floyd</code>大佬發明的，屬實佩服！
Floyd算法，俗稱插點法，不就一個點一個點插進去更新用到被插點距離嘛！
好啦，Floyd算法就介紹到這裡，如果對你有幫助，請動動小手點個贊吧！蟹蟹。也歡迎關注個人技術公衆号：<code>bigsai</code> 擷取最新分享。