Здравствуйте, Аня Ласточка.
Алгоритм Форда-Белмана

Приложение:
{Алгоритм Форда-Белмана}
var a : array [1..20,1..20] of word;{матрица смежности}
c, pred, fl, d : array [1..20] of word;{
c – массив кратчайших расстояний
pred – массив предыдущих вершин
fl – массив флагов
d – массив для записи пути
}

i, j, k, n, first, last : byte;
f : text;{переменная для открытия файла in.txt}
{процедура обхода графа вглубь – для поиска всех путей}
Procedure Dfs(x : word);
var i : byte;{локальная переменная}
begin
if x=last then {если конечная вершина, то выводим путь}
begin
write(first,' ');
for i:=1 to j do {выводим путь}
write(d[i],' ');
writeln;
exit;{выходим из процедуры}
end;
fl[x]:=1;{помечаем, что были в вершине}
for i:=1 to n do
if (fl[i]=0)and(a[x,i]<>32767) then
begin
inc(j);
d[j]:=i;{записываем в путь вершину}
dfs(i);{вызываемся от i-той вершины}
dec(j);
end;
fl[x]:=0;{помечаем, что вершина свободна}
end;
{Программа}
begin
assign(f,'in.txt');{открываем файл для чтения}
reset(f);
readln(f, n);{считываем количество вершин}
for i := 1 to n do
for j := 1 to n do
read(f, a[i,j]);{считываем матрицу смежности}
writeln('Matrix:');
for i:=1 to n do {выводим матрицу на экран}
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 {заменяем нули - бесконечностью}
for j:=1 to n do
if a[i,j]=0 then a[i,j]:=32767;
writeln('Введите 1 вершину');
readln(first);
writeln('Введите 2 вершину');
readln(last);
close(f);{zakrivaem file in.txt}
for j := 1 to n do
begin
c[j] := a[first,j];{Записываем начальные значения}
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 {если не бесконечность и путь более выгодный}
if (c[k] < 32767) and (c[k] + a[k,j] < c[j]) then
begin
c[j] := c[k] + a[k,j];{Записываем новое значение}
pred[j] := k;{Записываем предыдущую вершину}
end;
if c[last] = 32767 then writeln('Нет путей') else
begin
writeln;
writeln('Кратчайший путь:');
write(first,' ');
i := last;
k := 1;
while i <> first do {в обратном порядке обходим путь}
begin
d[k] := i;{записываем путь в массив}
k := k + 1;
i := pred[i];
end;
for i := k - 1 downto 1 do {выводим кратчайший путь}
write(d[i],' ');
writeln;
writeln('Все пути:');
j:=0;
Dfs(first);{вызываем процедуру поиска всех путей}
end;
readln;readln;{ждем нажатия клавиши}
end.