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



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


Пример 3.

Нахождение расстояний от источника до всех вершин в бесконтурном графе.

PROGRAM P_a_t_h;

const MaxNodes = 9;

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 ; { Начальная вершина пути (источник) }

u,v : NodePtr;

i,j,k : NodePtr;

{ ----------------------- }

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;

S:=1;

{ Инициализация }

For j:=2 to MaxNodes do D[j]:=B;

D[S]:=0;

{ Вычисление матрицы расстояний от источника до всех вершин графа }

For j:=2 to MaxNodes do

For i:=1 to MaxNodes do

If (A[i,j]<>0) AND (D[j]>D[i]+A[i,j])

then D[j]:=D[i]+A[i,j];

{ Вывод матрицы расстояний от источника до всех вершин графа }

WriteLn (' Матрица расстояний : ');

For i:=1 to MaxNodes do Write (D[i],' ');

WriteLn

END.

Проверьте работу программы для следующей путевой матрицы:

Приведенный алгоритм может найти применение в методах управ-ления выполнением проекта, называемых PERT ( Project Evaluation and Review Technique ) или CPM ( Critical Path Method ). Эти методы основываются на построении графа (сети PERT, сети CPM), дуги которого соответствуют некоторым элементарным задачам, составляющим проект, а их веса указывают на время, необходимое для решения отдельных задач. Кроме этого, мы предполагаем, что для произвольных дуг этого графа ( u,v ) и ( v,t ) задача, изображаемая дугой ( u,v ), должна быть закончена перед началом решения задачи, изображаемой дугой ( v,t ).


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