Компьютерные сети. Лабораторные работы



Система дорог - часть 3


путь 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];



Содержание  Назад  Вперед