簡介
Floyd-Warshall算法（Floyd-Warshall algorithm）枉阵，是一種利用動態(tài)規(guī)劃的思想尋找給定的加權圖中多源點之間最短路徑的算法，與Dijkstra算法類似预茄。該算法名稱以創(chuàng)始人之一兴溜、1978年圖靈獎獲得者、斯坦福大學計算機科學系教授羅伯特·弗洛伊德命名耻陕。
簡單的說就是解決任意兩點間的最短路徑的一種算法拙徽，可以正確處理有向圖或負權的最短路徑問題，同時也被用于計算有向圖的傳遞閉包诗宣。Floyd-Warshall算法的時間復雜度為O(N3)膘怕，空間復雜度為O(N2)。
解決最短路徑問題有幾個出名的算法:
1.dijkstra算法,最經(jīng)典的單源最短路徑算法
2.bellman-ford算法,允許負權邊的單源最短路徑算法
3.spfa,其實是bellman-ford+隊列優(yōu)化,其實和bfs的關系更密一點
4.floyd算法,經(jīng)典的多源最短路徑算法
今天先說說Floyd
Floyd算法詳解
描述
a）如圖：存在【0,1,2,3】 4個點召庞，兩點之間的距離就是邊上的數(shù)字岛心，如果兩點之間来破，沒有邊相連，則無法到達忘古，為無窮大徘禁。
b）要讓任意兩點（例如從頂點a點到頂點b）之間的路程變短，只能引入第三個點（頂點k）髓堪，并通過這個頂點k中轉即a->k->b送朱，才可能縮短原來從頂點a點到頂點b的路程。那么這個中轉的頂點k是0~n中的哪個點呢干旁？
算法過程
準備
1）如圖 0->1距離為5骤菠，0->2不可達，距離為∞疤孕，0->3距離為7……依次可將圖轉化為鄰接矩陣（主對角線商乎，也就是自身到自身，我們規(guī)定距離為0祭阀，不可達為無窮大）鹉戚，如圖矩陣 用于存放任意一對頂點之間的最短路徑權值。
2）再創(chuàng)建一個二維數(shù)組Path路徑數(shù)組专控，用于存放任意一對頂點之間的最短路徑抹凳。每個單元格的內容表示從i點到j點途經(jīng)的頂點。（初始還未開始查找伦腐，默認-1）
開始查找
1）列舉所有的路徑（自己到自己不算）
即為：
0 -> 1 , 0 -> 2 , 0 -> 3 ,
1 -> 0 , 1 -> 2 , 1 -> 3 ,
2 -> 0 , 1 -> 1 , 1 -> 3
轉化成二元數(shù)組即為：
{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}
從上面中二元組集合的第一個元素開始，循環(huán)執(zhí)行以下過程：
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搂誉，則判斷下一組二元數(shù)組。
3. 如果表達式為真静檬，更新A[ i ] [ j ]的值為A[ i ] [ 0 ] + A[ 0 ] [ j ]炭懊，Path[ i ] [ j ]的值為點0（即設置i到j要經(jīng)過0點中轉）
{0并级，1}按照此過程執(zhí)行之后，
0->0 + 0->1的距離不小于0->1 侮腹，下一組{0嘲碧，2}，{0父阻，3}愈涩， {1，0}加矛，{2履婉，0}，{3斟览，0}也同理毁腿。
{1，2}按照此過程執(zhí)行苛茂，A[1,0] 無窮大狸棍， A[0,2]也是無窮大，而A[1,4] = 4味悄，則1點到2點肯定不會從0點中轉草戈。
A[1][0]無窮大同理下一組{1，2}侍瑟， {1唐片，3}也同理。
{2涨颜，1}按照此過程執(zhí)行费韭，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）根據(jù)最終結果删窒，就可以知道任意2點的最短距離和路徑
比如1點到2點怎么走缤沦？根據(jù)路徑Path矩陣,Path[1][2] = 3，表示從點3中轉易稠，即 1-> 3 ->2
6）如果中轉點不止1個呢缸废？
有時候不只通過一個點，而是經(jīng)過兩個點或者更多點中轉會更短，即a->k1->k2b->或者a->k1->k2…->k->i…->b企量。
比如頂點1到頂點0测萎，我們看數(shù)組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 。
顯然湿蛔，這是一個逐層遞進膀曾，遞歸的過程。
算法實現(xiàn)
基本定義
// 表示無窮大 即不可達
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阳啥，請留言評論添谊。
