【最短路徑Floyd算法詳解推導過程】看完這篇，你還能不懂Floyd算法？還不會？...

簡介

 Floyd-Warshall算法（Floyd-Warshall algorithm），是一種利用動態規劃的思想尋找給定的加權圖中多源點之間最短路徑的算法，與Dijkstra算法類似。該算法名稱以創始人之一、1978年圖靈獎獲得者、斯坦福大學計算機科學系教授羅伯特·弗洛伊德命名。

簡單的說就是解決任意兩點間的最短路徑的一種算法，可以正確處理有向圖或負權的最短路徑問題，同時也被用于計算有向圖的傳遞閉包。Floyd-Warshall算法的時間復雜度為O(N3)，空間復雜度為O(N2)。

解決最短路徑問題有幾個出名的算法:

• 1.dijkstra算法,最經典的單源最短路徑算法

• 2.bellman-ford算法,允許負權邊的單源最短路徑算法

• 3.spfa,其實是bellman-ford+隊列優化,其實和bfs的關系更密一點

• 4.floyd算法,經典的多源最短路徑算法

今天先說說Floyd

Floyd算法詳解

描述

a）如圖：存在【0,1,2,3】 4個點，兩點之間的距離就是邊上的數字，如果兩點之間，沒有邊相連，則無法到達，為無窮大。?
b）要讓任意兩點（例如從頂點a點到頂點b）之間的路程變短，只能引入第三個點（頂點k），并通過這個頂點k中轉即a->k->b，才可能縮短原來從頂點a點到頂點b的路程。那么這個中轉的頂點k是0~n中的哪個點呢？

算法過程

準備

1）如圖 0->1距離為5，0->2不可達，距離為∞，0->3距離為7……依次可將圖轉化為鄰接矩陣（主對角線，也就是自身到自身，我們規定距離為0，不可達為無窮大），如圖矩陣 用于存放任意一對頂點之間的最短路徑權值。

2）再創建一個二維數組Path路徑數組，用于存放任意一對頂點之間的最短路徑。每個單元格的內容表示從i點到j點途經的頂點。（初始還未開始查找，默認-1）

開始查找

1）列舉所有的路徑（自己到自己不算）

即為：
0 -> 1 , 0 -> 2 , 0 -> 3 ,
1 -> 0 , 1 -> 2 , 1 -> 3 ,
2 -> 0 , 1 -> 1 , 1 -> 3
轉化成二元數組即為：
{0，1}，{0，2}，{0，3}，{1，0}，{1，2}，{1，3}，{2，0}，{2，1}，{2，3}，{3，0}，{3，1}，{3，2}

2）選擇編號為0的點為中間點

{0，1}，{0，2}，{0，3}，{1，0}，{1，2}，{1，3}，{2，0}，{2，1}，{2，3}，{3，0}，{3，1}，{3，2}
從上面中二元組集合的第一個元素開始，循環執行以下過程：

1. 用i，j兩個變量分別指向二元組里的兩個元素，比如{0，1}這個二元組，i指向0；j指向1
2. 判斷 (A[ i ][ 0 ]+A[ 0 ][ j ] ) < A[ i ][ j ] （即判斷 i -> j，i點到j點的距離是否小于從0點中轉的距離），如果false，則判斷下一組二元數組。
3. 如果表達式為真，更新A[ i ] [ j ]的值為A[ i ] [ 0 ] + A[ 0 ] [ j ]，Path[ i ] [ j ]的值為點0（即設置i到j要經過0點中轉）

{0，1}按照此過程執行之后，

0->0 + 0->1的距離不小于0->1 ，下一組{0，2}，{0，3}， {1，0}，{2，0}，{3，0}也同理。

{1，2}按照此過程執行，A[1,0] 無窮大， A[0,2]也是無窮大，而A[1,4] = 4，則1點到2點肯定不會從0點中轉。

A[1][0]無窮大同理下一組{1，2}， {1，3}也同理。

{2，1}按照此過程執行，A[2][0] = 3 ,A[0][1]=5 ，A[2][1] = 3那么 A[2][0]+ ,A[0][1] > A[2][1]
…………
依次類推，遍歷二元組集合，沒有0點適合做中轉的

3）選擇編號為1的點為中間點

4）選擇編號為2的點為中間點

依次類推，遍歷二元組集合{0，1}，{0，2}，{0，3}，{1，0}，{1，2}，{1，3}，{2，0}，{2，1}，{2，3}，{3，0}，{3，1}，{3，2}
，當遍歷{3，0}時，A[3][2] = 1 ,A[2][0]=3 ，A[3][0] = 不可達，那么 2點適合做從3點到0點之間的中轉點。
設置距離矩陣A[3][0] = 1+3 =4 ，Path矩陣Path[3][0] = 2點，表示從3到0在2點中轉，距離最近。

如圖表示（紅色單元格），從3到0，最近距離為4，在2點中轉 。

依次類推，遍歷完二元組集合

5）選擇編號為3的點為中間點，最終結果

依次類推，遍歷二元組集合，直到所有的頂點都做過一次中間點為止。

6）根據最終結果，就可以知道任意2點的最短距離和路徑

比如1點到2點怎么走？根據路徑Path矩陣,Path[1][2] = 3，表示從點3中轉，即 1-> 3 ->2

6）如果中轉點不止1個呢？

有時候不只通過一個點，而是經過兩個點或者更多點中轉會更短，即a->k1->k2b->或者a->k1->k2…->k->i…->b。
比如頂點1到頂點0，我們看數組Path
Path[1][0] = 3，說明頂點3是中轉點，那么再從3到0
Path[3][0] = 2，說明從3到0，頂點2是中轉點，然后在從2到0
Path[2][0] = -1，說明頂點2到頂點0沒有途徑頂點，也就是說，可以由頂點2直接到頂點0，即它們有邊連接。

最終，最短路徑為1->3->2->0，距離為 A[1][0] = 6 。
顯然，這是一個逐層遞進，遞歸的過程。

算法實現

基本定義

    //    表示無窮大 即不可達public static int MAX = Integer.MAX_VALUE;//    距離矩陣public int[][] dist;//    路徑Path矩陣public int[][] path;

核心算法

//        核心算法for(int k = 0 ; k < size ; k++){for(int i = 0;i < size;i++){for(int j = 0 ;j < size;j++){
//                判斷如果 ik距離可達且 kj距離可達 且 i和j的距離是否大于 i-> k 與 k->j的距離和if( dist[i][k] != MAX &&  dist[k][j] != MAX  &&  dist[i][j] > (dist[i][k] + dist[k][j]) ){path[i][j]= k;dist[i][j]= dist[i][k] + dist[k][j];}}}}

運行結果

源碼下載

Floyd算法java實現-源碼下載

Floyd算法java實現

看完這篇文章如果你還不會Floyd，請留言評論。