floydwarshall演算法

① floyd-warshanll演算法是什麼啊

Floyd-Warshall演算法是解決任意兩點間的最短路徑的一種演算法。
Floyd-Warshall演算法的描述如下： for k:=1 to n do 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-Warshall 演算法用來找出每對點之間的最短距離。它需要用鄰接矩陣來儲存邊，這個演算法通過考慮最佳子路徑來得到最佳路徑。
注意單獨一條邊的路徑也不一定是最佳路徑。
從任意一條單邊路徑開始。所有兩點之間的距離是邊的權，或者無窮大，如果兩點之間沒有邊相連。
對於每一對頂點 u 和 v，看看是否存在一個頂點 w 使得從 u 到 w 再到 v 比己知的路徑更短。如果是更新它。
不可思議的是，只要按排適當，就能得到結果。 // 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)
這個演算法的效率是O(V^3)。它需要鄰接矩陣來儲存圖。
這個演算法很容易實現，只要幾行。
即使問題是求單源最短路徑，還是推薦使用這個演算法，如果時間和空間允許(只要有放的下鄰接矩陣的空間，時間上就沒問題)。
計算每一對頂點間的最短路徑（floyd演算法）
【例題】設計公共汽車線路(1) 現有一張城市地圖，圖中的頂點為城市，有向邊代表兩個城市間的連通關系，邊上的權即為距離。現在的問題是，為每一對可達的城市間設計一條公共汽車線路，要求線路的長度在所有可能的方案里是最短的。
輸入： n (城市數，1≤n≤20) e (有向邊數1≤e≤210) 以下e行，每行為邊（i,j）和該邊的距離wij（1≤i,j≤n）
輸出： k行，每行為一條公共汽車線路
分析：本題給出了一個帶權有向圖，要求計算每一對頂點間的最短路徑。這個問題雖然不是圖的連通性問題，但是也可以借鑒計算傳遞閉包的思想：在枚舉途徑某中間頂點k的任兩個頂點對i和j時，將頂點i和頂點j中間加入頂點k後是否連通的判斷，改為頂點i途徑頂點k至頂點j的路徑是否為頂點i至頂點j的最短路徑（1≤i，j，k≤n）。 顯然三重循環即可計算出任一對頂點間的最短路徑。設 n—有向圖的結點個數； path—最短路徑集合。其中path[i，j]為vi至vj的最短路上vj的前趨結點序號(1≤i，j≤n)； adj—最短路徑矩陣。初始時為有向圖的相鄰矩陣
我們用類似傳遞閉包的計算方法反復對adj矩陣進行運算，最後使得adj成為存儲每一對頂點間的最短路徑的矩陣 (1≤i，j≤n) Var adj：array[1‥n，1‥n] of real； path：array[1‥n，1‥n] of 0‥n；
計算每一對頂點間最短路徑的方法如下：
首先枚舉路徑上的每一個中間頂點k（1≤k≤n）；然後枚舉每一個頂點對（頂點i和頂點j，1≤i，j≤n）。如果i頂點和j頂點間有一條途徑頂點k的路徑，且該路徑長度在目前i頂點和j頂點間的所有條途徑中最短，則該方案記入adj[i，j]和path[i，j] adj矩陣的每一個元素初始化為∞；
for i←1 to n do {初始時adj為有向圖的相鄰矩陣，path存儲邊信息} for j←1 to n do if wij<>0 then begin adj[i，j]←wij； path[i，j]←j； end{then} else path[i，j]←0； for k←1 to n do {枚舉每一個中間頂點} for i←1 to n do {枚舉每一個頂點對} for j←1 to n do if adj[i，k]+adj[k，j]<adj[i，j]{若vi經由vk 至vj的路徑目前最優，則記下} then begin adj[i，j]←adj[i，k]+adj[k，j]； path[i，j]←path[k，j]； end，{then} 計算每一對頂點間最短路徑時間復雜度為W(n3)。演算法結束時，由矩陣path可推知任一結點對i、j之間的最短路徑方案是什麼 Procere print(i，j)； begin if i=j then 輸出i else if path[i，j]=0 then 輸出結點i與結點j之間不存在通路 else begin print (i，path[i，j])； {遞歸i頂點至j頂點的前趨頂點間的最短路徑} 輸出j； end；{else} end；{print} 由此得出主程序 距離矩陣w初始化為0； 輸入城市地圖信息（頂點數、邊數和距離矩陣w）； 計算每一對頂點間最短路徑的矩陣path； for i←1 to n do {枚舉每一個頂點對} for j←1 to n do if path[i，j]<>0 {若頂點i可達頂點j，則輸出最短路徑方案} then begin print（i，j）； writeln； end；{then}