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

       

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


Система дорог [Касьянов,Сабельфельд,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);



{ Помещение 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];

D[S]:=0;

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

For k:=1 to MaxNodes-2 do

For i:=1 to MaxNodes do

If i<>S

then For j:=1 to MaxNodes do

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

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

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

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

WriteLn ;

{ Нахождение кратчайшего пути из S в T с помощью }

{ построенной матрицы расстояний }

Write ('Введите конечную вершину пути: '); ReadLn (T);

Stack:=Nil; V__S_t_a_c_k (Stack,T); v:=T;

While v<>S do

begin

For i:=1 to MaxNodes do

If D[v]=D[i]+A[i,v] then u:=i;

V__S_t_a_c_k (Stack,u); v:=u

end ;

{ Вывод кратчайшего пути на экран дисплея }

Write ('Кратчайший путь: '); UkZv:=Stack ;

While UkZv<>Nil do

begin Write (UkZv^.Element,' '); UkZv:=UkZv^.Sled end;

WriteLn

END.

Рассмотрим тестовый пример [Евстигнеев,Мельников,1981]. Вычислить кратчайшее расстояние между вершинами s и t в сети:

(s,a,4), (s,d,6), (a,d,-3), (a,b,8), (b,t,2), (a,e,5),

(d,e,2), (e,c,3), (d,c,11), (c,b,-4), (c,t,7), (b,d,-6).

Перенумеруем вершины следующим образом:

(s,1), (a,2), (d,3), (b,4), (c,5), (e,6), (t,7),

а затем выпишем матрицу весов дуг

и применим алгоритм Форда-Беллмана к этой матрице. В результате получим:

Введите источник: 1

Матрица расстояний: 0 4 -4 2 1 -2 4

Введите конечную вершину пути: 7

Кратчайший путь: ...

Компьютер "зависает", ибо в графе имеется контур отрицательной длины 3-6-5-4 (его длина -6+2+3-4=-5), что приводит к появлению бесконечного множества путей, каждый из которых "короче" предыдущего, например:



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



D[S]:=0; Q:=[];

For i:=1 to MaxNodes do Q:=Q+[i];

Q:=Q-[S];

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

While Q<>[] do

begin

Min:=B;

For i:=1 to MaxNodes do

If (i IN Q) AND (D[i]<Min)

then begin Min:=D[i]; u:=i end;

Q:=Q-[u];

For i:=1 to MaxNodes do

If i IN Q

then If D[i]>D[u]+A[u,i]

then D[i]:=D[u]+A[u,i]

end ;

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

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

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

WriteLn ;

{ Нахождение кратчайшего пути из S в T }

Write ('Введите конечную вершину пути: '); ReadLn (T);

Stack:=Nil; V__S_t_a_c_k (Stack,T); v:=T;

While v<>S do

begin

For i:=1 to MaxNodes do

If D[v]=D[i]+A[i,v] then u:=i;

V__S_t_a_c_k (Stack,u); v:=u

end ;

{ Вывод кратчайшего пути на экран дисплея }

Write ('Кратчайший путь: '); UkZv:=Stack ;

While UkZv<>Nil do

begin Write (UkZv^.Element,' '); UkZv:=UkZv^.Sled end;

WriteLn

END.

Приведем контрпример к алгоритму Дейкстры [Евстигнеев, Мель-ников , 1981]: вычислим кратчайшее расстояние между вершинами s и t в сети: ( s , a ,4),( s , d ,6), ( a , d ,-3), ( a , b ,8), ( b , t ,2), ( a , e ,5), ( d , e ,2), ( e , c ,3), ( d , c ,11), ( c , b ,-4), ( c , t ,7), ( b , d ,-6). Заметим, что мы допустили существование отри-цательных весов!

Перенумеруем вершины: (s,1),(a,2),(d,3),(b,4),(c,5),(e,6),(t,7), а затем

выпишем матрицу весов дуг:

и применим алгоритм Дейкстры к этой матрице. В результате получим:

Введите источник: 1

Матрица расстояний: 0 4 1 2 6 3 4

Введите конечную вершину пути: 7

Кратчайший путь: 1 2 3 6 5 4 7

Однако, как уже было отмечено ранее, в графе имеется контур отрицательной длины 3-6-5-4 (его длина -6+2+3-4=-5), что приводит к появлению бесконечного множества путей, каждый из которых "короче" предыдущего, например:

путь 1-2-3-6-5-4-7 с длиной 4,

путь 1-2-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 и т.д.

Таким образом, кратчайший путь алгоритмом Дейкстры определить нельзя, так как в графе имеется контур отрицательной длины.



Пример 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 ).


Легко заметить, что такой граф должен быть бесконтурным .

Нашей задачей является нахождение самого длинного пути из вер-шины s , соответствующей началу проекта, до вершины t , соответствующей его окончанию. Такой путь называется критическим. Его длина определяет время, необходимое для реализации всего проекта. Эта задача сводится к задаче о кратчайшем пути путем изменения знака каждого веса A( u,v ), где u -> v , на обратный. Так, например, выполните предыдущую программу для следующей путевой матрицы:

Пример 4 [Библиотека,1975,с.100-104].

Планирование критического пути (анализ сети ПЕРТ).

PROGRAM C_r_i_t_P_a_t_h;

{ Автор алгоритма : Leavenworth B. (CACM,1961,3) }

type Massiv = Array [1..20] of Integer;

var n : Integer ; { Общее количество работ по проекту }

{ (количество ребер ориентированного графа) }

i : Massiv ; { Вектор-пара, представляющая k-ю работу, }

j : Massiv ; { которая понимается как стрелка, связыва - }

{ ющая событие i [ k ] с событием j [ k ] }

{ Граф задан массивом ребер: }

{ ( i [1], j [1]),( i [2], j [2]),...,( i [ n ], j [ n ]) }

{ Должно быть выполнено: }

{ i [1]=1, i [ k ]< i [k+1], i [ k ]< j [ k ] }

dij : Massiv ; { dij [ k ] - продолжительность k-й операции }

s1 : Massiv ; { s1[ k ] - самый ранний срок начала k-й }

{ операции }

s2 : Massiv ; { s2[ k ] - самый поздний срок начала k-й }

f1 : Massiv ; { f1[ k ] - самый ранний срок завершения k-й }

f2 : Massiv ; { f2[ k ] - самый поздний срок завершения k-й }

{ операции }

tf : Massiv ; { tf [ k ] - полный резерв времени k-й операции}

ff : Massiv ; { ff [ k ] - свободный резерв времени k-й }

{ операции }

k : Integer ; { Параметр цикла }

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

PROCEDURE C_r_i_t_i_c_a_l_P_a_t_h (n: Integer; i: Massiv;

j: Massiv; dij: Massiv;

var s1,s2,f1,f2,tf,ff: Massiv);

var k,index,max,min: Integer;

ti,te : Massiv;

BEGIN

index:=1;

For k:=1 to n do

begin

If i[k]=index+1 then index:=i[k];

ti[k]:=0; te[k]:=9999

end;



For k:=1 to n do

begin

max:=ti[i[k]]+dij[k];

If ti[j[k]]<max then ti[j[k]]:=max

end;

te[j[n]]:=ti[j[n]];

For k:=n downto 1 do

begin

min:=te[j[k]]-dij[k];

If te[i[k]]>min then te[i[k]]:=min

end;

For k:=1 to n do

begin

s1[k]:=ti[i[k]]; f1[k]:=s1[k]+dij[k];

f2[k]:=te[j[k]]; s2[k]:=f2[k]-dij[k];

tf[k]:=f2[k]-f1[k]; ff[k]:=ti[j[k]]-f1[k]

end

END;

{ --- }

BEGIN

Write (' Введите общее количество работ по проекту: ');

ReadLn (n);

For k:=1 to n do

begin

Write ('Вводите начало, конец дуги и продолжительность: ');

ReadLn (i[k],j[k],dij[k])

end;

C_r_i_t_i_c_a_l_P_a_t_h (n,i,j,dij,s1,s2,f1,f2,tf,ff);

{ Вывод результатов }

Write ('Самый ранний срок начала : ');

For k:=1 to n do Write (s1[k]:2,' '); WriteLn;

Write ('Самый поздний срок начала : ');

For k:=1 to n do Write (s2[k]:2,' '); WriteLn;

Write ('Самый ранний срок завершения : ');

For k:=1 to n do Write (f1[k]:2,' '); WriteLn;

Write ('Самый поздний срок завершения: ');

For k:=1 to n do Write (f2[k]:2,' '); WriteLn;

Write ('Свободный резерв времени : ');

For k:=1 to n do Write (ff[k]:2,' '); WriteLn;

Write ('Полный резерв времени : ');

For k:=1 to n do Write (tf[k]:2,' '); WriteLn;

{ Определение критического пути. Критический путь задается }

{ стрелками, соединяющими события, для которых полный ре- }

{ зерв времени равен нулю }

Write ('Критический путь: '); Write (1,' ');

For k:=1 to n do

If tf[k]=0 then Write (j[k],' ')

END.


Содержание раздела