Взял материал: http://algolist.manual.ru/maths/graphs/shortpath/floyd.php
Попытался спрограммировать:
| Код |
var
d, p, buf: array [1..5, 1..5] of integer;
i,j: integer;
m: integer;
s: string;
begin
for i:=1 to 5 do
for j:=1 to 5 do
begin
p[i,j]:=i;
if (i = j) then
d[i,j]:=0
else
d[i,j]:=MaxInt;
end;
d[1,2]:=1;
d[2,3]:=2;
d[3,4]:=3;
d[4,5]:=4;
m:=0;
while m < 5 do
begin
for i:=1 to 5 do
for j:=1 to 5 do
if (i <> j) then
begin
buf[i,j]:=Min(d[i,j], d[i, m+1] + d[m+1,j]);
if (d[i,j] > d[i,m+1] + d[m+1,j]) then
p[i,j]:=p[m+1,j]
end
else
buf[i,j]:=0;
d:=buf;
inc(m)
end;
for i:=1 to 5 do
begin
s:='';
for j:=1 to 5 do
s:=s + IntToStr(p[i,j]) + ' ';
Memo1.Lines.Add(s);
s:='';
for j:=1 to 5 do
s:=s + IntToStr(d[i,j]) + ' ';
Memo2.Lines.Add(s)
end
end;
|
В итоге (см. обозначения по ссылке) получил:
Матрица D:
| Цитата |
0 1 -13 -11 -7
-15 0 -14 -12 -8
-13 -2147483648 0 -10 -6
-11 -2147483648 -10 0 -4
-7 -2147483648 -6 -4 0
|
Матрица P:
| Цитата |
1 1 1 1 1
2 2 1 1 1
2 1 3 1 1
2 1 1 4 1
2 1 1 1 5
|
Такое впечатление, что работает не верно...  |