warshall演算法

『壹』 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}

『貳』 最短路徑問題5種類型

最短路徑問題5種類型有Dijkstra演算法、A*演算法、SPFA演算法、Bellman-Ford演算法和Floyd-Warshall演算法，

擴展知識：

用於解決最短路徑問題的演算法被稱做「最短路徑演算法」，有時被簡稱作「路徑演算法」。最常用的路徑演算法有：
Dijkstra演算法、A*演算法、SPFA演算法、Bellman-Ford演算法和Floyd-Warshall演算法，本文主要介紹其中的三種。
最短路徑問題是圖論研究中的一個經典演算法問題，旨在尋找圖（由結點和路徑組成的）中兩結點之間的最短路徑。
演算法具體的形式包括：確定起點的最短路徑問題：即已知起始結點，求最短路徑的問題。
確定終點的最短路徑問題：與確定起點的問題相反，該問題是已知終結結點，求最短路徑的問題。在無向圖中該問題與確定起點的問題完全等同，在有向圖中該問題等同於把所有路徑方向反轉的確定起點的問題。
確定起點終點的最短路徑問題：即已知起點和終點，求兩結點之間的最短路徑。

『叄』 Warshall演算法求傳遞閉包

#include <stdio.h>
#include <stdlib.h>
#define N 20
#define M 20

main()
{
int i,j,k,m,n;
int r1[M],r2[M],a[N],mr[N][N]={0};

FILE * fp;
printf("程序自動調用c:/stone2.txt文件內相應數據\n");
fp=fopen("c:\\stone2.txt","r");
fscanf(fp,"%d",&n); /*讀取集合元素個數*/
for(i=0;i<n;i++) /*讀取集合元素*/
fscanf(fp,"%d",&a[i]);
fscanf(fp,"%d",&m); /*讀取關系個數*/
for(k=0;k<m;k++)
fscanf(fp,"%d,%d",&r1[k],&r2[k]); /*讀取關系*/

fclose(fp);

printf("自反閉包r(R):\n{");
for(i=0;i<n;i++) printf("<%d,%d>,",a[i],a[i]); /*輸出自反閉包*/
for(k=0;k<m;k++)
{
if(r1[k]!=r2[k]) printf("<%d,%d>,",r1[k],r2[k]);
else continue;
}
printf("\b}\n");

printf("對稱閉包s(R):\n{"); /*輸出對稱閉包*/
for(k=0;k<m;k++)
{
if(r1[k]!=r2[k]) printf("<%d,%d>,<%d,%d>,",r1[k],r2[k],r2[k],r1[k]);
else printf("<%d,%d>,",r1[k],r2[k]);
}
printf("\b}\n");

k=0;
for(i=0;i<n,k<m;i++)
{
if(r1[k]!=a[i]) continue;
else
{
for(j=0;j<n,k<m;j++) /*關系轉換成矩陣*/
{
if(r2[k]!=a[j]) continue;
else
{
mr[i][j]=1;
k++; i=0;j=0;
break;
}
}
}
}

printf("關系所對應的關系矩陣:\n");
for(i=0;i<n;i++)
{ /*列印關系矩陣*/
for(j=0;j<n;j++)
printf("%5d",mr[i][j]);
printf("\n");
}
for(k=0;k<n;k++)
for(i=0;i<n;i++) /*warshall*/
for(j=0;j<n;j++)
mr[i][j]+=mr[i][j]+mr[i][k]*mr[k][j];

for(i=0;i<n;i++)
for(j=0;j<n;j++)
{ /*把mr[]非0項賦值為1*/
if(!mr[i][j]) continue;
else mr[i][j]=1;
}

printf("傳遞閉包對應關系矩陣:\n");
for(i=0;i<n;i++)
{ /*輸出傳遞閉包對應的關系矩陣*/
for(j=0;j<n;j++)
printf("%5d",mr[i][j]);
printf("\n");
}

system("PAUSE");

}
自己寫的,三個閉包都有,包括傳遞閉包,看注釋就知道了,還是用文件讀寫,方便數據輸入