Алгоритм Флойда. Поиск Кратчайшего пути.

[Shady]

Вообщем мне нужна реализация алгоритма Флойда по поиску кратчайшего пути между точками графа на Delphi. Так же нужна инфа по самому этому алгоритму, если у кого-то есть хоть что-нить, либо знает где найти пишите. Заренее спасибо.
P.S. Курсяк мой горит) Аж сминим пламенем)

[kommunist]

Дано: непyстой взвешенный гpаф G=(V, E) с пpоизвольными весами ребер (дуг). Требуется найти длины кpатчайших пyтей между всеми парами вершин графа, если в графе нет циклов (контуров) отрицательной суммарной длины, либо обнаружить наличие таких контуров.

Инициализация:

1. Построим матрицу D0 размерности |V| x |V|, элементы которой определяются по правилу:

dii0= 0;
dij0= Weight(vi, vj), где i<>j, если в графе существует ребро (дуга) (vi, vj);
dij0= бесконечность , где i<>j, если нет ребра (дуги) (vi, vj).
2. m:=0.
Основная часть:

1. Построим матрицу Dm+1 по Dm, вычисляя ее элементы следующим образом:
dijm+1=min{dijm, di(m+1)m + d(m+1)jm}, где i<>j; diim+1=0 (*).
Если dimm + dmim < 0 для какого-то i, то в графе существует цикл (контур) отрицательной длины, проходящий через вершину vi; ВЫХОД.
2. m:=m+1; если m<|V|, то повторяем шаг (1), иначе элементы последней построенной матрицы D|V| равны длинам кратчайших путей между соответствующими вершинами; ВЫХОД.

Если требует найти сами пути, то перед началом работы алгоритма построим матрицу P с начальными значениями элементов pij=i. Каждый раз, когда на шаге (1) значение dijm+1 будет уменьшаться в соответствии с (*) (т.е. когда di(m+1)m + d(m+1)jm<dijm), выполним присваивание pij:=p(m+1)j. В конце работы алгоритма матрица P будетопределять кратчайшие пути между всеми парами вершин: значение pij будет равно номеру предпоследней вершины в пути между i и j (либо pij=i, если путь не существует).
Примечаниe: если граф - неориентированный, то все матрицы Dm являются симметричными, поэтому достаточно вычислять элементы, находящиеся только выше (либо только ниже) главной диагонали.

Если не поможет тогда вот:

[Shady]

Прога работать отказывается. Ругается на что-то.

[kommunist]

Const
NN=100;
Type
Graph = array[1..nn,1..nn] of longint; {граф задан матрицей смежности}
Var
n:integer;
Procedure Floyd (var a:graph; c:graph; var p:graph);
var i,j,k:integer;
begin
for i:=1 to n do
for j:=1 to n do begin a[i,j]:=c[i,j]; p[i,j]:=0; end;
for i:=1 to n do a[i,i]:=0;
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] begin
a[i,j]:=a[i,k]+a[k,j];
p[i,j]:=k;
end;
end;

procedure ReadGraph(var a:graph); 
var
i,j:integer;
begin
write('n= ');readln(n);
For i:=1 to n do for j:=1 to n do
begin write('G',i,',',j,'= ');readln(a[i,j]); end;
writeln;
end;

procedure ReadFileGraph(var a:graph);
var
i,j:integer; filename:string; f:text;
begin
Write('Enter file name:'); readln(filename);
Assign (f,filename); reset(f);
Readln(f,N);
For i:=1 to n do for j:=1 to n do read(f,a[i,j]); close(f);
end;

var
a,c,p:graph;
i,j:integer;
begin
{ ReadGraph( c );}
ReadFileGraph( c ); 
floyd(a,c,p);
writeln('---------------------------');
for i:=1 to n do {
begin
for j:=1 to n do write(a[i,j]:3);
writeln
end;
writeln('---------------------------');
for i:=1 to n do
begin
for j:=1 to n do write(p[i,j]:3);
writeln
end;
readln;
end.

где
В программе C-граф, заданный матрицей смежности.
A- матрица содержащая кратчайшие пути.
P - матрица, сохраняющая маршруты.

[ВитальК]

http://kontrolnaya-rabota.ru/s/kalkulyator/-сайт решает всё по математике

[Андрей Арловский]

Сообщение от Shady

Прога работать отказывается. Ругается на что-то.

у меня тоже не работает (((