Пути в бесконтурном графе

Для бесконтурного графа с произвольными весами дуг задача нахождения кратчайшего пути может быть решена за О(m) шагов. Рассмотрим модельный бесконтурный граф (рис. 10.5).

Рис. 10.5. Модельный граф

Любой бесконтурный граф обладает следующим свойством: его вершины можно перенумеровать так, что любая дуга будет идти от вершины с меньшим номером к вершине с большим номером.

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

Рис. 10.6. Правильная нумерация

Доказательством этого свойства будет служить алгоритм правильной нумерации.

Алгоритм основывается на следующем простом факте: в бесконтурном графе существует хотя бы одна вершина, в которую не заходит ни одна дуга (иначе бы в графе существовал контур).

Все такие вершины соберем в стек. Затем

1) вытолкнем из стека произвольную вершину;

2) присвоим ей номер 1;

3) удалим ее из графа вместе со всеми выходящими из нее дугами.

После операции удаления дуг могут появиться новые вершины, в которые не заходит ни одна дуга. Эти вершины помещаются в стек, затем из стека выталкивается произвольная вершина, ей присваивается следующий номер и т.д.

Понятно, что в результате получится правильная нумерация, так как любая вершина u получает номер в тот момент, когда оставшиеся еще незанумерованные вершины v (позже они получат большие номера) либо не соединены дугами с u, либо дуга идет в направлении (u→v).

Не так очевидно, почему все вершины получат номера:

если из стека удалили последнюю вершину, а в графе, получившемся после удаления этой вершины и выходящих из нее дуг, все вершины имеют заходящие в них дуги, то они уже никогда не попадут в стек и никогда не получат номера.

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

Поскольку из стека выталкивается произвольная вершина, то принцип стека не является обязательным и выбран только для удобства.

АЛГОРИТМ {Правильная нумерация}

Данные: Бесконтурный орграф G=<V,E>, заданный списками инцидентности SLED[v], v Î V.

Результаты: Для каждой вершины v новый номер NN[v] такой, что номера NN[v] являются правильной нумерацией графа G.

1 begin

{INP[v] – число дуг, заходящих в вершину v}

2 for vÎV do INP[v]:= 0;

3 for uÎV do

4 for vÎSLED[u] do

{находим все вершины v, для которых (u→v)}

5 INP[v]:= INP[v]+1;

6 СТЕК:= 0;

7 for vÎV do

8 if INP[v]=0 then СТЕК Ü v;

9 num:= 0; {текущий номер}

10 while СТЕК <> 0 do

11 begin

12 u Ü СТЕК;

13 num:= num+1;

14 NN[u]:= num;

15 for vÎSLED[u] do

16 begin

17 INP[v]:= INP[v]–1;

18 if INP[v]=0 then СТЕК Ü v;

19 end;

20 end;

21 end.

Все дуги графа анализируются два раза: в цикле 3–5 для подсчета числа заходящих дуг INP[v], в цикле 10–20, где удаление дуг из графа заменено уменьшением чисел INP[v].

Таким образом, вычислительная сложность алгоритма пропорциональна числу дуг, т.е. равна О(m) шагов.

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

Так как все дуги идут из вершины с меньшим номером в вершину с большим номером, то промежуточные вершины на пути от 1 до j будут иметь номера, меньшие j. Поэтому для нахождения кратчайшего расстояния D[j] нужно знать только D[2],…,D[j-1]. Идея алгоритма следующая: зная D[1] (оно равно 0), вычислить D[2]; зная D[1] и D[2], вычислить D[3] и т.д.

АЛГОРИТМ {Расстояния в бесконтурном графе}

Данные: Орграф G=<V,E> с правильной нумерацией, заданный списками PRED[v], матрица весов A[u,v], u,vÎV.

Результаты: Расстояния D[v] от источника 1 до всех остальных v Î V.

1 begin

2 D[1]:= 0;

3 for j:=2 to n do D[j]:= +¥;

4 for j:=2 to n do

5 for iÎPRED[j] do

6 D[j]:= min(D[j], D[i]+A[i,j]);

7 end.

В цикле 4–6 каждая дуга анализируется ровно один раз, поэтому вычислительная сложность алгоритма равна О(m) шагов.

Бесконтурный граф может служить математической моделью для задач управления выполнением проектов. Дуги графа соответствуют элементарным задачам, составляющим проект, веса дуг – времени, необходимому для выполнения элементарной задачи. Вершина s соответствует началу выполнения проекта, вершина t – его завершению. Для любых двух дуг (u→v) и (v→p) предполагается, что задача (u→v) должна быть закончена до начала выполнения задачи (v→p). Самый длинный путь от s до t требует времени, минимально необходимого для выполнения всего проекта.

Вопрос. Каким образом можно воспользоваться процедурой поиска кратчайшего пути для нахождения самого длинного пути?

Ответ. Изменить веса дуг на противоположные. Граф бесконтурный, поэтому контуры отрицательного веса в нем не появятся.

Алгоритм Флойда

Для решения задачи о кратчайших расстояниях между всеми парами вершин можно воспользоваться алгоритмом Форда –Беллмана, применив его n раз к каждой из вершин. Однако существует более эффективный алгоритм, который решает ту же задачу за О(n³) шагов.

Идея алгоритма следующая: будем искать кратчайшие расстояния D[i,j], постепенно увеличивая количество промежуточных вершин в пути от i до j. За начальные приближения возьмем пути от i до j без промежуточных вершин, т.е. веса ребер A[i,j].

Пусть уже известны длины D[i,j] самых коротких путей между всеми парами вершин, имеющих промежуточные вершины из множества 1...k-1. Добавим теперь к множеству промежуточных вершин вершину k. Путь от i до j будет складываться из пути от i до k и пути от k до j (рис. 10.7).

Рис. 10.7. Добавление промежуточной вершины

Так как наши пути не могут содержать повторяющихся вершин (иначе бы они не были кратчайшими), то пути от i до k и от k до j среди промежуточных вершин могут иметь только вершины из множества 1...k-1. Длины таких путей нам известны по предположению, поэтому длина пути от i до j, проходящего через k, сложится как сумма D[i,k]+D[k,j]. Остается сравнить старое значение D[i,j] с этой суммой и в качестве окончательного значения выбрать минимальное. Алгоритм заканчивает работу, когда промежуточными вершинами могут быть все вершины графа.

АЛГОРИТМ Флойда

Данные: Орграф G=<V,E>, матрица весов A[u,v], u,vÎV.

Результаты: Расстояния DD[i,j] между всеми парами вершин i, j ÎV.

1 begin

2 for i:=1 to n do

3 for j:=1 to n do DD[i,j]:= A[i,j];

4 for i:=1 to n do DD[i,i]:= 0;

5 for k:=1 to n do

6 for i:=1 to n do

7 for j:=1 to n do

8 DD[i,j]:= min(DD[i,j], DD[i,k]+DD[k,j]);

9 end.

Очевидно, что тройной цикл дает вычислительную сложность О(n³).

Вопрос. Измените алгоритм печати пути исходя из того, что имеется двумерный массив расстояний DD[i,j].

Ответ. Чтобы найти путь от s до t в процедуру печати пути вместо одномерного массива D расстояний нужно передавать s-ю строку двумерного массива DD.