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



Система дорог


Система дорог [Касьянов,Сабельфельд,1986,с.97-98] - это размеченный мультиграф (без петель), который отличается от графа тем, что в нем одна и та же пара (различных) вершин может быть связана более чем одним ребром. При этом вершины соответствуют городам, а ребра - дорогам. Односторонним дорогам соответствуют дуги, а двусторонним дорогам - ребра.

Каждая дорога имеет некоторую длину - положительное вещественное число. Понятие пути, достижимости и замкнутого пути определяются для системы дорог аналогично подобным понятиям для графа и ориентированного графа. Длина пути в системе дорог - это сумма длин дорог этого пути. Расстояние между двумя городами - это длина минимального пути между этими городами.

4. Ход работы

Пример 1.

Нахождение расстояния от источника до всех вершин (метод Форда-Беллмана ). Нахождение кратчайшего пути из S в T.

PROGRAM F _ o _ r _ d __ B _ e _ l _ l _ m _ a _ n ;

const MaxNodes = 5;

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 ; { Конечная вершина пути }

u,v : NodePtr;

i,j,k : NodePtr;

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);



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