Floyd-Warshall算法，簡稱Floyd算法，用于求解任意兩點間的最短距離，時間複雜度為O(n^3)。
使用條件&範圍
通常可以在任何圖中使用，包括有向圖、帶負權邊的圖。
Floyd-Warshall 算法用來找出每對點之間的最短距離。它需要用鄰接矩陣來儲存邊，這個算法通過考慮最佳子路徑來得到最佳路徑。
1.注意單獨一條邊的路徑也不一定是最佳路徑。
2.從任意一條單邊路徑開始。所有兩點之間的距離是邊的權，或者無窮大，如果兩點之間沒有邊相連。
對于每一對頂點 u 和 v，看看是否存在一個頂點 w 使得從 u 到 w 再到 v 比己知的路徑更短。如果是更新它。
3.不可思議的是，隻要按排适當，就能得到結果。
僞代碼:
//dist(i,j) 為從節點i到節點j的最短距離
For i←1 to n do
For j←1 to n do
dist(i,j) = weight(i,j)
For k←1 to n do // k為“媒介節點”
For i←1 to n do
For j←1 to n do
if (dist(i,k) + dist(k,j) < dist(i,j)) then // 是否是更短的路徑？
dist(i,j) = dist(i,k) + dist(k,j)
我們平時所見的Floyd算法的一般形式如下：
voidFloyd(){
int i,j,k;
for(k=1;k<=n;k++)
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
if(dist[i][k]+dist[k][j]<dist[i][j])
dist[i][j]=dist[i][k]+dist[k][j];
}
注意下第6行這個地方，如果dist[i][k]或者dist[k][j]不存在，程式中用一個很大的數代替。最好寫成if(dist[i] [k]!=INF && dist[k][j]!=INF &&dist[i][k]+dist[k][j]
Floyd算法的實作以及輸出最短路徑和最短路徑長度，具體過程請看【動畫示範Floyd算法】。
代碼說明幾點：
1、A[][]數組初始化為各頂點間的原本距離，最後存儲各頂點間的最短距離。
2、path[][]數組儲存最短路徑，與目前疊代的次數有關。初始化都為-1，表示沒有中間頂點。在求A[i][j]過程中，path[i][j]存放從頂點vi到頂點vj的中間頂點編号不大于k的最短路徑上前一個結點的編号。在算法結束時，由二維數組path的值回溯，可以得到從頂點vi到頂點vj的最短路徑。
初始化A[][]數組為如下，即有向圖的鄰接矩陣。
POJ2253-Frogger
題目大意:
給出兩隻青蛙的坐标A、B，和其他的n-2個坐标，任一兩個坐标點間都是雙向連通的。顯然從A到B存在至少一條的通路，每一條通路的元素都是這條通路中前後兩個點的距離，這些距離中又有一個最大距離。
現在要求求出所有通路的最大距離，并把這些最大距離作比較，把最小的一個最大距離作為青蛙的最小跳遠距離。
Floyd算法
用Floyd算法求出兩兩最短路，再求出從每個點開始的最長路，最後從這n個最長路中求出最小的那個即為所求。