путь 1-2-3-6-5-4-7 с длиной 4,
путь 1-20-3-6-5-4-3-6-5-4-7 с длиной -1,
путь 1-2-3-6-5-4-3-6-5-4-3-6-5-4-7 с длиной -6 и т.д.
Алгоритмом Форда-Беллмана определить кратчайший путь нельзя.
Пример 2.
Нахождение расстояния от источника до всех вершин в графе с неотрицательными весами (метод Дейкстры ). Нахождение кратчайшего пути из S в T.
PROGRAM D _ i _ j _ k _ s _ t _ r _ a ;
const MaxNodes = 6;
B = 1000; { Машинный эквивалент "бесконечности" 7 0}
type NodePtr = 1.. MaxNodes ;
Matrix = Array [NodePtr,NodePtr] of Integer;
Matrix1 = Array [NodePtr] of Integer;
{ Описание типа узла стека }
TipElement = NodePtr;
svqz = ^Zveno;
Zveno = Record
Element: TipElement;
Sled: svqz
end;
var A : Matrix; { Матрица весов дуг }
D : Matrix1; { Матрица расстояний от источника }
{ до всех вершин графа }
S : NodePtr ; { Начальная вершина пути (источник) }
T : NodePtr ; { Конечная вершина пути }
Q : Set of NodePtr;
u,v : NodePtr;
i,j,k : NodePtr;
Min : Integer;
Stack : svqz ; { Указатель на рабочий стек }
UkZv : svqz;
{ ---------------------------------------------------------- }
PROCEDURE U_d_a_l_e_n_i_e (var Stack: svqz; var Klad: TipElement);
{ Удаление элемента из стека Stack и сохранение его в Klad }
var q: svqz;
BEGIN
If Stack=Nil
then WriteLn ('Попытка выбора из пустого стека!')
else begin
Klad:=Stack^.Element; q:=Stack; Stack:=Stack^.Sled;
Dispose (q)
end
END;
{ ---------------------------------------------------------- }
PROCEDURE V__S_t_a_c_k (var Stack: svqz; Elem: TipElement);
{ Помещение Elem в стек Stack }
var q: svqz;
BEGIN
New (q); q^.Element:=Elem; q^.Sled:=Stack; Stack:=q
END;
{ --- }
BEGIN
{ Ввод матрицы весов дуг заданного графа }
WriteLn ('Вводите элементы матрицы весов дуг по стро-кам :');
For i:=1 to MaxNodes do
For j:=1 to MaxNodes do
begin
Write (' Введите A[',i,',',j,']: ');
ReadLn (A[i,j]);
If A[i,j]=0 then A[i,j]:=B
end ;
Write ('Введите источник: '); ReadLn ( S );
{ Инициализация }
For i:=1 to MaxNodes do D[i]:=A[S,i];