Случай бесконтурной сети.
В этом случае, так же как и в случае сетей с неотрицательными весами дуг, известен более эффективный алгоритм вычисления расстояний от фиксированного узла до всех остальных, чем алгоритм Форда-Беллмана. В основе этого алгоритма лежат следующие две леммы.
Лемма6.2. В каждом бесконтурном орграфе имеется хот? бы один узел, степень исхода которого равна нулю.
Напомним, что степенью исхода узла называется число дуг из него выходящих. Пусть w1 — произвольный узел орграфа. Выберем, если это возможно, произвольный узел w2 такой, что (w1, w2) E, затем w3 так, что (w2, w3) E, и т.д. до тех пор, пока подобный выбор узла возможен. Через конечное число шагов мы дойдем до некоторого узла w*, из которого не выходит ни одна дуга, ибо в бесконтурном орграфе узлы в строящемся пути w1→w2→w3→..., не могут повторяться. Следовательно, последний построенный в пути w* узел имеет нулевую степень исхода.
Лемма 6.3.Узлы бесконтурного ориентированного графа можно перенумеровать так, что каждая дуга идет из узла с меньшим номером в узел с большим номером.
Орграфы с так пронумерованными узлами иногда называют топологически отсортированными, а алгоритм, осуществляющий такую нумерацию узлов — алгоритмом топологической сортировки узлов.
Для доказательства леммы 6.3 приведем алгоритм, осуществляющий топологическую сортировку. Неформально этот алгоритм можно сформулировать следующим образом.
1. Объявить наибольшим неиспользованным номером число, равное количеству узлов в орграфе.
2. Выбрать произвольный узел v, степень исхода которого равна нулю, и присвоить узлу v наибольший из еще не использованных номеров. Номер, который получит узел v, считать использованным.
3. Удалить из орграфа узел v вместе со всеми входящими в него дугами.
4. Повторять шаги 2 и 3 до тех пор, пока все узлы не получат свой новый номер.
Корректность работы приведенного алгоритма топологической сортировки вытекает из леммы 6.2, так как при каждом удалении узла новый граф остается бесконтурным, и, следовательно, в нем также существует узел с нулевой степенью исхода.
При формальном описании этого алгоритма переменная НОМЕР дает значение самого большого из еще не использованных номеров. Переменная ИСХОД[v] указывает на текущее значение степени исхода узла v. В частности, удаление узла v V вместе со всеми выходящими из v дугами приводит к уменьшению значения ИСХОД[w] на единицу для всех w ПРЕДШ[v]. СТЕК служит для накопления текущего множества узлов, имеющих нулевую степень исхода.
Массив ИНДЕКС предназначен для хранения новых номеров вершин.
В этом параграфе нам будет удобнее считать, что все сети и орграфы заданы списками смежностей ПРЕДШ[v].
АЛГОРИТМ 6.5. ТОПСОРТ
Данные: Бесконтурный орграф G=(V.E), заданный списками смежностей ПРЕДШ[v], v V.
Результаты: Массив ИНДЕКС длины n такой, что для любой дуги (v,w) E справедливо неравенство ИНДЕКС[у]<ИНДЕКС[w].
В алгоритме 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).
При описании алгоритма вычисления расстояний в бесконтурной сети будем считать, что все узлы заданной сети топологически отсортированы, то есть каждая дуга сети выходит из узла с меньшим номером и входит в узел с большим номером. Расстояния будем вычислять от узла v1=s.
Пусть vk — произвольный узел заданной бесконтурной сети. Тогда любой s-vk-путь проходит через узлы с меньшими чем к номерами. Из этого замечания следует, что для вычисления расстояний от s до всех остальных узлов сети достаточно последовательно вычислять расстояния от s до v1, затем от s до v2 и так далее. Пусть, как и в предыдущих параграфах, d(v) обозначает расстояние от s до v. Тогда d(v1) = 0, и если d(vr) для всех r < k вычислено, то для определения d(vk) имеем формулу
d[vk] = min{D[vr]+c(vr, vk): r =1,2,..,k}. (6.5)
Корректность формулы (6.5)легко проверяется методом математической индукции.
Именно по формуле (6.5)вычисляет расстояния от вершины s=V] предлагаемый ниже алгоритм 6.6.
АЛГОРИТМ 6.6
(* Вычисление расстояний от узла V; в бесконтурной сети *)
Данные: Бесконтурная сеть G=(V,E,c) с топологически отсортированными узлами, заданная списками ПРЕДШ[v], v V.
Результаты: Расстояния D[v] от v1 до всех v V.
Теорема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] |
∞ | ∞ | ∞ | ∞ | ∞ | ||
∞ | ∞ | ∞ | ∞ | |||
∞ | ∞ | ∞ | ||||
∞ | ∞ | |||||
∞ | ||||||
-4 |
Рис.6.4. Работа алгоритма 6.6
Рекомендуем читателям разобраться с тем, что может произойти, если в алгоритме 6.6 убрать строку 3, а строку 6 записать следующим образом: D[vk]:= min(D[w]+c(w,vk)).
В случае задания бесконтурной сети списками СЛЕД расстояния от v1 до всех остальных узлов также могут быть вычислены за время О(m). Такой алгоритм получается легкой модификацией алгоритма 6.6. Предоставляем читателям возможность самостоятельно подправить алгоритм 6.6 для достижения указанной цели.
В заключение отметим, что все три основных алгоритма (Форда-Беллмана, Дейкстры и алгоритм 6.6) вычисления расстояний от фиксированного узла легко могут быть модифицированы для вычисления расстояний от фиксированного узла в сетях со взвешенными узлами (см. задачи 6.1 и 6.2).
Дата добавления: 2021-07-22; просмотров: 379;