前言

在圖論中，在尋路最短路徑中除了Dijkstra算法以外，還有Floyd算法也是非常經(jīng)典，然而兩種算法還是有區(qū)別的，Floyd主要計算多源最短路徑。

在單源正權(quán)值最短路徑，我們會用Dijkstra算法來求最短路徑，并且算法的思想很簡單——貪心算法:每次確定最短路徑的一個點然后維護(更新)這個點周圍點的距離加入預(yù)選隊列，等待下一次的拋出確定。但是雖然思想很簡單，實現(xiàn)起來是非常復(fù)雜的，我們需要鄰接矩陣(表)儲存長度，需要優(yōu)先隊列(或者每次都比較)維護一個預(yù)選點的集合。還要用一個boolean數(shù)組標記是否已經(jīng)確定、還要---------

總之，Dijkstra算法的思想上是很容易接受的，但是實現(xiàn)上其實是非常麻煩的。但是單源最短路徑?jīng)]有更好的辦法。復(fù)雜度也為O(n2)

而在n節(jié)點多源最短路徑中,如果從Dijkstra算法的角度上，只需要將Dijkstra封裝，然后執(zhí)行n次Dijkstra算法即可,復(fù)雜度為O(n3)。但是這樣感覺很臃腫，代碼量巨大，占用很多空間內(nèi)存。有沒有啥方法能夠稍微變變口味呢？

答案是有的，這就是易寫但稍需要理解的Floyd算法。一個求多元最短路徑算法。

算法介紹

先看看百度百科的定義吧：

Floyd算法又稱為插點法，是一種利用動態(tài)規(guī)劃的思想尋找給定的加權(quán)圖中多源點之間最短路徑的算法，與Dijkstra算法類似。該算法名稱以創(chuàng)始人之一、1978年圖靈獎獲得者、斯坦福大學(xué)計算機科學(xué)系教授羅伯特·弗洛伊德命名。

簡單的來說，算法的主要思想是動態(tài)規(guī)劃(dp)，而求最短路徑需要不斷松弛(熟悉spfa算法的可能熟悉松弛)。

而算法的具體思想為：

鄰接矩陣dist儲存路徑，同時最終狀態(tài)代表點點的最短路徑。如果沒有直接相連的兩點那么默認為一個很大的值(不要溢出)！而自己的長度為0.

從第1個到第n個點依次加入圖中。每個點加入進行試探是否有路徑長度被更改。

而上述試探具體方法為遍歷圖中每一個點(i,j雙重循環(huán))，判斷每一個點對距離是否因為加入的點而發(fā)生最小距離變化。如果發(fā)生改變，那么兩點(i,j)距離就更改。

重復(fù)上述直到最后插點試探完成。

其中第三步的狀態(tài)轉(zhuǎn)移方程為:

• dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j])
  其中dp[x][y]的意思可以理解為x到y(tǒng)的最短路徑。所以dp[i][k]的意思可以理解為i到k的最短路徑dp[k][j]的意思可以理解為k到j(luò)的最短路徑.

咱們圖解一個案例：

默認的最短長度初始為鄰接矩陣初始狀態(tài)

• 加入第一個節(jié)點1,大家可以發(fā)現(xiàn)，由于1的加入，使得本來不連通的2，3點對和2，4點對變得聯(lián)通，并且加入1后距離為當前最小。(可以很直觀加入5之后2，4，更短但是還沒加入)。為了更好的描述其實此時的直接聯(lián)通點多了兩條。(2,3)和(2,4).我們在dp中不管這個結(jié)果是通過前面那些步驟來的，但是在這個狀態(tài)，這兩點的最短距離就算它！
  
• 同時你可以發(fā)現(xiàn)加入1其中也使得3,1,4這樣聯(lián)通，但是 3,1,4聯(lián)通的話距離為9遠遠大于本來的(3,4)為2，所以不進行更新。
• 咱們繼續(xù)加入第二個節(jié)點。在加入的初始態(tài)為：
  
• 進行遍歷插入看看是否更新節(jié)點
  
  實際上這個時候圖中的連線就比較多了。當然這些連線都是代表當前的最短路徑。 這也和我們的需求貼合，我們最終要的是所有節(jié)點的最短路徑。每個節(jié)點最終都應(yīng)該有6條指向不同節(jié)點的邊！ 表示鄰接矩陣的最終結(jié)果。

至于算法的模擬兩部核心已經(jīng)告訴大家了，大家可以自行模擬剩下的。

程序?qū)崿F(xiàn)

而對于程序而言，這個插入的過程相當簡單。核心代碼只有四行！
代碼如下

public class floyd {static int max = 66666;// 別Intege.max 兩個相加越界為負public static void main(String[] args) {int dist[][] = {{ 0, 2, 3, 6, max, max }, { 2, 0, max, max,4, 6 }, { 3, max, 0, 2, max, max },{ 6, max, 2, 0, 1, 3 }, { max, 4, max, 1, 0, max }, { max, 6, max, 3, max, 0 } };// 地圖// 6個for (int k = 0; k < 6; k++)// 加入滴k個節(jié)點{for (int i = 0; i < 6; i++)// 松弛I行{for (int j = 0; j < 6; j++)// 松弛i列{dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]);}}}// 輸出for (int i = 0; i < 6; i++) {System.out.print("節(jié)點"+(i+1)+" 的最短路徑");for (int j = 0; j < 6; j++) {System.out.print(dist[i][j]+" ");}System.out.println();}} }

結(jié)果為：

可以自行計算，圖和上篇的Dijkstra是一致的，大家可以自行比對，結(jié)果一致，說明咱么的結(jié)果成功的。

當然，在你學(xué)習(xí)的過程中，可以在每加入一個節(jié)點插入完成后，打印鄰接矩陣的結(jié)果，看看前兩部和筆者的是否相同(有助于理解)，如果相同，則說明正確！

你可能還會有疑惑，那咱么就用一個局部性來演示一下，看其中AB最短距離變化情況祝你理解：

好啦，Floyd算法就介紹到這里，如果對你有幫助，請動動小手點個贊吧！蟹蟹。
希望和各位共同進步！歡迎關(guān)注筆者公眾號：bigsai!

總結(jié)

以上是生活随笔為你收集整理的短小精悍的多源最短路径算法—Floyd算法的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。