§3. Случай бесконтурной сети.

В этом случае, так же как и в случае сетей с неотрицательны­ми весами дуг, известен более эффективный алгоритм вычисле­ния расстояний от фиксированного узла до всех остальных, чем алгоритм Форда-Беллмана. В основе этого алгоритма лежат сле­дующие две леммы.

Лемма 6.2. В каждом бесконтурном орграфе имеется хот? бы один узел, степень исхода которого равна нулю.

Напомним, что степенью исхода узла называется число дуг из него выходящих. Пусть w₁ — произвольный узел орграфа. Выберем, если это возможно, произвольный узел w₂ такой, что (w₁, w₂)E, затем w₃ так, что (w₂, w₃)E, и т.д. до тех пор, пока подобный выбор узла возможен. Через конечное число шагов мы дойдем до некоторого узла w*, из которого не выходит ни одна дуга, ибо в бесконтурном орграфе узлы в строящемся пути w₁→w₂→w₃→..., не могут повторяться. Следовательно, послед­ний построенный в пути w* узел имеет нулевую степень исхода.

Лемма 6.3. Узлы бесконтурного ориентированного графа можно перенумеровать так, что каждая дуга идет из узла с мень­шим номером в узел с большим номером.

Орграфы с так пронумерованными узлами иногда называют топологически отсортированными, а алгоритм, осуществляю­щий такую нумерацию узлов — алгоритмом топологической сортировки узлов.

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

1. Объявить наибольшим неиспользованным номе­ром число, равное количеству узлов в орграфе.

2. Выбрать произвольный узел v, степень исхода которого равна нулю, и присвоить узлу v наибольший из еще не использованных номеров. Номер, который получит узел v, считать использованным.

3. Удалить из орграфа узел v вместе со всеми вхо­дящими в него дугами.

4. Повторять шаги 2 и 3 до тех пор, пока все узлы не получат свой новый номер.

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

При формальном описании этого алгоритма переменная НО­МЕР дает значение самого большого из еще не использованных номеров. Переменная ИСХОД[v] указывает на текущее значение степени исхода узла v. В частности, удаление узла vV вместе со всеми выходящими из v дугами приводит к уменьшению значе­ния ИСХОД[w] на единицу для всех wПРЕДШ[v]. СТЕК слу­жит для накопления текущего множества узлов, имеющих нуле­вую степень исхода.

Массив ИНДЕКС предназначен для хранения новых номеров вершин.

В этом параграфе нам будет удобнее считать, что все сети и орграфы заданы списками смежностей ПРЕДШ[v].

АЛГОРИТМ 6.5. ТОПСОРТ

Данные: Бесконтурный орграф G=(V.E), заданный списками смежностей ПРЕДШ[v], vV.

Результаты: Массив ИНДЕКС длины n такой, что для любой дуги (v,w)E справедливо неравенство ИНДЕКС[у]<ИНДЕКС[w].

1. begin

2. for vV doИСХОД[v]:=0;

3. for vV do

4. for wПРЕДШ[v] do ИСХОД|w]:=ИСХОД[w]+1;

5. CTEK:=Ø; HOMEP:=n:

6. for vV do

7. if ИСХОД[v]=0 then СТЕК cv;

8. while CTEK=Ø do

9. begin

10. v СТЕК; СТЕК;

11. ИНДЕКС[v]:=НОМЕР; HOMEP:=HOMEP-1;

12. for wПРЕДШ[v] do

13. begin ИСХОД[w]:=ИСХОД[w]-1;

14. if ИСХОД[w]=0 then СТЕКw

15. end;

16. end;

17. end.

В алгоритме 6.5 в цикле в строках 3 и 4 вычисляется степень исхода каждого узла. Затем все узлы с нулевой степенью исхода помещаются в СТЕК (цикл 6-7). В строках 10 и 11 очередному узлу присваивается наибольший из неиспользованных номеров, иначе говоря, реализуется шаг 2 неформального описания алго­ритма. Цикл в строках 12-15 обеспечивает удаление последнего пронумерованного узла вместе с дугами ему инцидентными, и все узлы, степень исхода которых в новом орграфе равна нулю, сразу же помещаются в СТЕК (шаг 3 неформального описания).

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

Теорема 6.4. Алгоритм ТОПСОРТ имеет сложность 0(т).

Напомним, что на протяжении этой главы мы условились считать, что m>n. Циклы в строках 2 и 6-7 анализируют каждый узел ровно по одному разу, а в строках 3-4 и 12-15 — каждую ду­гу также ровно по одному разу. Следовательно, сложность алго­ритма 6.5 есть 0(n)+0(m)=0(m).

В тех случаях, когда бесконтурный орграф задан списками смежностей СЛЕД, топологическая сортировка узлов орграфа также может быть осуществлена за время О(т) (см. задачу 6.4).

При описании алгоритма вычисления расстояний в бесконтурной сети будем считать, что все узлы заданной сети топологиче­ски отсортированы, то есть каждая дуга сети выходит из узла с меньшим номером и входит в узел с большим номером. Расстоя­ния будем вычислять от узла v₁=s.

Пусть v_k — произвольный узел заданной бесконтурной сети. Тогда любой s-v_k-путь проходит через узлы с меньшими чем к номерами. Из этого замечания следует, что для вычисления рас­стояний от s до всех остальных узлов сети достаточно последова­тельно вычислять расстояния от s до v₁, затем от s до v₂ и так да­лее. Пусть, как и в предыдущих параграфах, d(v) обозначает рас­стояние от s до v. Тогда d(v₁) = 0, и если d(v_r) для всех r < k вы­числено, то для определения d(v_k) имеем формулу

d[v_k] = min{D[v_r]+c(v_r, v_k): r =1,2,..,k}. (6.5)

Корректность формулы (6.5) легко проверяется методом ма­тематической индукции.

Именно по формуле (6.5) вычисляет расстояния от вершины s=V] предлагаемый ниже алгоритм 6.6.

АЛГОРИТМ 6.6

(* Вычисление расстояний от узла V; в бесконтурной сети *)

Данные: Бесконтурная сеть G=(V,E,c) с топологически отсорти­рованными узлами, заданная списками ПРЕДШ[v], vV.

Результаты: Расстояния D[v] от v₁ до всех vV.

1. begin

2. D[v₁]:=0

3. for k:=2 to n do D[v_k]:=

4. for k:=2 to n do

5. for wПРЕДШ[v] do

6. D[v_k] := min(D[v_k], D[w]+c(w,v_k))

7. end.

Теорема 6.5. Алгоритм 6.6 имеет сложность O(m)

Цикл в строке 3 требуетn операций присваивания. Цикл в строках 4-6 приводит к тому, что каждая дуга сети анализируется ровно один раз, и каждый анализ дуги приводит к выполнению фиксированного числа операций в строке 6. Следовательно, сложность алгоритма 6.6 есть O(n)+O(m)=O(m).

k	D[v1]	D[v2]	D[v3]	D[v4]	D[v5]	D[v6]
	0	∞	∞	∞	∞	∞
2		4	∞	∞	∞	∞
3			11	∞	∞	∞
4				3	∞	∞
5					2	∞
6						-4

Рис.6.4. Работа алгоритма 6.6

Рекомендуем читателям разобраться с тем, что может про­изойти, если в алгоритме 6.6 убрать строку 3, а строку 6 записать следующим образом: D[v_k]:= min(D[w]+c(w,v_k)).

В случае задания бесконтурной сети списками СЛЕД расстоя­ния от v₁ до всех остальных узлов также могут быть вычислены за время О(m). Такой алгоритм получается легкой модификацией алгоритма 6.6. Предоставляем читателям возможность самостоя­тельно подправить алгоритм 6.6 для достижения указанной цели.

В заключение отметим, что все три основных алгоритма (Форда-Беллмана, Дейкстры и алгоритм 6.6) вычисления рас­стояний от фиксированного узла легко могут быть модифициро­ваны для вычисления расстояний от фиксированного узла в сетях со взвешенными узлами (см. задачи 6.1 и 6.2).