定义

思想

实现

总评

图文

定义

Floyd-Warshall 算法用来找出每对点之间的最短距离。它需要用邻接矩阵来储存边，这个算法通过考虑最佳子路径来得到最佳路径。 注意单独一条边的路径也不一定是最佳路径。

思想

从任意一条单边路径开始。所有两点之间的距离是边的权，或者无穷大，如果两点之间没有边相连。

对于每一对顶点 u 和 v，看看是否存在一个顶点 w 使得从 u 到 w 再到 v 比己知的路径更短。如果是更新它。

实现

Pascal程序：

for i:= 1 to n do

for j:= 1 to n do

read(f[i,j]);

for k:= 1 to n do

for i:= 1 to n do

for j:= 1 to n do

if (i<>j)and(i<>k)and(j<>k)and(f[i,k]+f[k,j]<f[i,j]) then

f[i,j]:=f[i,k]+f[k,j];

总评

时间复杂度O(n^3),只要有存下邻接矩阵的空间，时间一般没问题，并且不必担心负权边的问题。

图文

弗洛耶德算法（Floyed算法）：

基本思想：求解所有点间的路径需要进行n次试探。对于顶点i到顶点j的路径长度，首先考虑让路径经过顶点1，比较路径（i，j）和（i，1，j）的长度取其短者为当前求得的最短路径长度。对每一对顶点的路径都做这样的试探，则可求得一个矩阵设为A(1)，求n次即得每对顶点间的最短路径A(n)。A(0)=A：邻接矩阵。如下图：

程序如下：

program floyed;

const n=4;

var

cost,a:array[1..n,1..n]of integer;

p:array[1..n,1..n] of 0..n;

i,j,k:integer;

procedure init;

var i,j:integer;

begin

for i:=1 to n do

for j:=1 to n do

begin

read(cost[i,j]);

a[i,j]:=cost[i,j];

p[i,j]:=0;

end;

end;

procedure path(i,j:integer);

var k:integer;

begin

k:=p[i,j];

if k<>0 then begin path(i,k);write('->',k);path(k,j);end

end;

begin

init;

for k:=1 to n do

for i:=1 to n do

for j:=1 to n do

if a[i,k]+a[k,j]<a[i,j] then

begin

a[i,j]:=a[i,k]+a[k,j];

p[i,j]:=k;

end;

for i:=1 to n do

for j:=1 to n do

if i<>j then

begin

writeln('a[',i,',',j,']=',a[i,j]);

write(i);

path(i,j);

writeln('->',j)

end;

end.

注意：弗洛耶德算法（Floyed算法）思想可用与判断有向图中任意两点是否连通？算法如下：

for k:=1 to n do

for i:=1 to n do

for j:=1 to n do

if （a[i,k]=1）and (a[k,j]=1) then a[i,j]=1 (a[i,j]=1表示i可达j，a[i,j]=0表示i不可达j）。