Алгоритм Форда-Беллмана для работы со взвешенными графами

{Bellman-Ford algorithm}
var a : array [1..20,1..20] of word;{matrica cmegnosti}
c, pred, fl, d : array [1..20] of word;{
c - massiv kratchayshih rastoyaniy
pred - massiv predidushih vershin
fl - massiv flagov
d - massiv dlya zapisi puti
}
 
i, j, k, n, first, last : byte;
f : text;{peremennaya dlya otkritiya file in.txt}
{procedura obhoda grafa vglub - dlya poiska vseh putey}
Procedure Dfs(x : word);
var i : byte;{lokalnay peremennaya}
begin
if x=last then {esli konechnaya vershina to vivodim put}
begin
write(first,' ');
for i:=1 to j do {vivodim put}
write(d[i],' ');
writeln;
exit;{vyhodim iz proceduri}
end;
fl[x]:=1;{pomechaem chto bili v vershine}
for i:=1 to n do
if (fl[i]=0)and(a[x,i]<>32767) then
begin
inc(j);
d[j]:=i;{zapisivaem v put vershiny}
dfs(i);{vizivaemsya ot i-oy vershini}
dec(j);
end;
fl[x]:=0;{pomechaem chto vershina svobodna}
end;
{Osnovnaya programma}
begin
assign(f,'in.txt');{otkrivaem file dlya chteniya}
reset(f);
readln(f, n);{shitivaem kol-vo vershin}
for i := 1 to n do
for j := 1 to n do
read(f, a[i,j]);{shitivaem matricy smegnosti}
writeln('Matrix:');
for i:=1 to n do  {vyvodim matricy na ekran}
for j:=1 to n do
if j=n then writeln(a[i,j]) else write(a[i,j],' ');
for i:=1 to n do {zamenyaem nuli - beskonechnostuy}
for j:=1 to n do
if a[i,j]=0 then a[i,j]:=32767;
writeln('Vvedite 1 vershiny');
readln(first);
writeln('Vvedite 2 vershiny');
readln(last);
close(f);{zakrivaem file in.txt}
for j := 1 to n do
begin
c[j] := a[first,j];{zapisivaem nachalnie znacheniya}
if a[first,j] < 32767 then
pred[j] := first;
end;
for i := 3 to n do
for j := 1 to n do
if j <> first then
for k := 1 to n do  {esli ne beskonechnost i put bolee vygodniy}
if (c[k] < 32767) and (c[k] + a[k,j] < c[j]) then
begin
c[j] := c[k] + a[k,j];{zapisivaem novoe znachenie}
pred[j] := k;{zapisivaem pred vershiny}
end;
if c[last] = 32767 then writeln('Net putey') else
begin
writeln;
writeln('Kratchaishiy put:');
write(first,' ');
i := last;
k := 1;
while i <> first do {v obratnom poryadke obhodim put}
begin
d[k] := i;{zapisivaem put v massiv}
k := k + 1;
i := pred[i];
end;
for i := k - 1 downto 1 do {vyvodim kratchayishiy put}
write(d[i],' ');
writeln;
writeln('Vse puti:');
j:=0;
Dfs(first);{vizivaem procedury poiska vseh putey}
end;
readln;readln;{gdem nagatiya klavishi}
end.