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