Алгоритмы - построение и анализ (1021735), страница 137
Текст из файла (страница 137)
Если же таких циклов нет, алгоритм выдает кратчайшие пути и их вес. В этом алгоритме используется ослабление, в результате которого величина 0 1с], представляющая собой оценку веса кратчайшего пути из истока а к каждой из вершин е Е Ъ', уменьшается до тех пор, пока она не станет равна фактичесюму весу кратчайшего пути б (з, е). Значение ткт!к возвращается алгоритмом Глава 24. Кратчайшие пути из одной вершины 673 и Рнс. 24.4. Выполнение алгоритма Беллмаиа-Форда тогда и только тогда, когда граф не содержит циклов с отрицательным весом, достижимых из истока. Веы.мАтч РОк0(С, ш, з) 1 1ьлт!АМЕБ Бпчпье БООксе(С, 3) 2 аког г' - 1 Го [У[С)[ — 1 3 бо аког (для) каждого ребра (и, о) Е Е[С] 4 бо ВЕЬАХ(и, о, и) 5 аког (для) каждого ребра (и, и) Е Е[С) б йо Ыг1[й> 0[и]+ш(и,и) 7 тпеп гетпгп РАьзе 8 гетнгп ВШЕ На рис.
24.4 проиллюстрирована работа алгоритма Веь МАм Ропп с графом, содержащим 5 вершин, в котором исток находится в вершине а. Рассмотрим, как работает алгоритм. После инициализации в строке 1 всех значений Н и я, алгоритм осуществляет [Ц вЂ” 1 проходов по ребрам графа. Каждый проход соответствует одной итерации цикла Рог в строках 2-4 и состоит из однократного ослабления каждого ребра графа.
После [Ц вЂ” 1 проходов в строках 5-8 проверяется наличие цикла с отрицательным весом и возвращается соответствующее булево значение. (Причины, по которым эта проверка корректно работает, стануг понятными несколько позже.) В примере, приведенном на рис. 24.4, алгоритм Беллман-Форд возвращает значение тКОЕ. Часть Ч!. Алгоритмы для работы с графами 674 На рис. 24.4 в вершинах графа показаны значения атрибутов Н на каждом этапе работы алгоритма, а выделенные ребра указывают на значения предшественников: если ребро (и, о) выделено, то я [о] = и. В рассматриваемом примере при каждом проходе ребра ослабляются в следующем порядке: (1, х), (1, у), (г, г), (х,1), (у,х), (у, в), (х, х), (в, в), (в, г), (в,у). В части а рисунка показана ситуация, сложившаяся непосредственно перед первым проходом по ребрам.
В частях б-д проиллюстрирована ситуация после каждого очередного прохода по ребрам. Значения атрибутов И и я, приведенные в части д, являются окончательными. Алгоритм Беллмана-Форда завершает свою работу в течение времени О ('и' Е), поскольку инициализация в строке 1 занимает время О (Ъ'), на каждый из [Ц вЂ” 1 проходов по ребрам в строках 2-4 требуется время О (Е), а на выполнение цикла !ог в строках 5-7 — время О (Е).
Чтобы доказать корректность алгоритма Беллмана-Форда, сначала покажем, что при отсутствии циклов с отрицательным весом он правильно вычисляет веса кратчайших путей для всех вершин, достижимых из истока. Лемма 24.2. Пусть С = (1г, Е) — взвешенный ориентированный граф с истоком в и весовой функцией ю: Š— Н., который не содержит циклов с отрицательным весом, достижимых из вершины в. Тогда по завершении [Ц вЂ” 1 итераций цикла Гог в строках 2-4 алгоритма Впььмкм Ропп, для всех вершин о, достижимых из вершины в, выполняется равенство д [о] = б (в, о).
Доказательство. Докажем сформулированную лемму, воспользовавшись свойством ослабления пути. Рассмотрим произвольную вершину о, достижимую из вершины ж Пусть р = (оо, оы..., оь), где ио = в и оь = о — кратчайший ациклический путь из вершины в в вершину о. Путь р содержит не более [Ъ'] — 1 ребер, так что 1с < ٠— 1. При каждой из ]'и'] — 1 итераций цикла !ог в строках 2-4 ослабляются все [Е[ ребер. Среди ребер, ослабленных во время г-й итерации (г = = 1, 2,..., /с), находится ребро (о; ы о;).
Поэтому, согласно свойству ослабления путей, выполняется цепочка равенств г1[о] = д[оь] = б(в,оь) = б(в,о). ° Следствие 24.3. Пусть С = (Ъ; Е) — взвешенный ориентированный граф с истоком в и весовой функцией ю: Š— К. Тогда для каждой вершины о е Ъ' путь из вершины в в вершину о существует тогда и толью тогда, когда после обработки графа С процедурой Впььмлм Р0кп выполняется неравенство Н [и] < оо. Доказательство. Доказательство этого следствия предлагается выполнить в ка- честве упражнения 24.1-2. Теорема 24.4 (Корректность алгоритма Беллмана-Форда). Пусть алгоритм Вега.мха Ропп обрабатывает взвешенный ориентированный граф С = (и',Е) с истоком в и весовой функцией ы: Š— К.
Если граф С не содержит циклов Глава 24. Кратчайшие пути из одной вершины 675 с отрицательным весом, достижимых из вершины в, то этот алгоритм возвращает значение тк11н, для всех вершин о е ъ' выполняется равенство ы [о] = о (в, о) и подграф предшествования С является деревом кратчайших путей с корнем в вершине в. Если же граф С содержит цикл с отрицательным весом, достижимый из вершины в, то алгоритм возвращает значение глин. Доказательство. Предположим, что граф С не содержит циклов с отрицательным весом, достижимых из источника в.
Сначала докажем, что по завершении работы алгоритма для всех вершин о е У выполняется равенство Й [о] = д (в, о). Если вершина о достижима из источника в, то доказательством этого утверждения служит лемма 24.2. Если же вершина о не достижима из вершины в, то это утверждение следует из свойства отсутствия пути. Таким образом, данное утверждение доказано.
Из свойства подграфа предшествования и этого утверждения следует„ что граф ф— дерево кратчайших путей. А теперь с помощью обоснованного выше утверждения покажем, что алгоритм Вн1,армян РОкп возвращает значение ткал. По завершении работы алгоритма для всех ребер (и,о) е Е выполняется соотношение И[о] = б(в,о) < б(в,о) + ю(ио) = И[и]+ ю(ио), где неравенство следует из неравенства треугольника. Поэтому ни одна из проверок, выполненных в строке б, не приведет к тому, что алгоритм Внл.млн Ронтз возвратит значение гл~.зш Следовательно, ему ничего не остается, как возвратить значение тлцн. Теперь предположим, что граф С содержит цикл с отрицательным весом, достижимый из истока в; пусть это будет цикл с = (ос, оы..., оь), где оо = оы Тогда ь ~> ю(о; ыо;) < О. 1=1 Чтобы воспользоваться методом "от противного*', предположим, что алгоритм Вв.1.млн Рокп возвращает значение ткал.
Тогда для г = 1, 2,..., к выполняются неравенства 0[о;] < 0[о; 1]+ ю(о; ыо;). Просуммировав неравенства по всему циклу с, получим: ~ ~[о*] < ~И[о*-1]+ю(о-~ о')) =, '1[о-~]+,'),ю(о'-ьо'). Поскольку ос = оь каждая вершина в цикле с в каждой сумме 2 ~ 0[о;] и 2„, П [о, 1] появляется ровно по одному разу, так что ь Часть Ч1. Алгоритмы для работы с графами 676 Кроме того, согласно следствию 24.3, атрибут с([е;] при г = 1,2,..., й принимает конечные значения. Таким образом, справедливо неравенство ь 0 < ~~> ю (сг ы п,), что противоречит неравенству (24.1). Итак, мы приходим к выводу, что алгоритм Внгл.млм Роко возвращает значение ткиЕ, если граф С не содержит циклов с отрицательным весом, достижимых из истока, и значение РАг,зн — в противном случае.
И Упражнения 24.1-1. Опишите работу алгоритма ВнььмАм Роко с ориентированным графом, показанным на рис. 24.4, в котором в качестве истока используется вершина з. В процессе каждого прохода ослабление ребер должно выполняться в том же порядке, что и на рисунке. Составьте список значений, которые принимают атрибуты г( и я после каждого прохода. А теперь измените вес ребра (з, х), присвоив ему значение 4, и выполните алгоритм снова, используя в качестве истока вершину ж 24.1-2. Докажите следствие 24.3.
24.1-3. Пусть дан взвешенный ориентированный граф О = (г', Е), который не содержит циклов с отрицательным весом. Для каждой пары вершин и, с Е "г' найдем минимальное количество ребер в кратчайшем пути от и к и (длина пути определяется его весом, а не количеством ребер). Пусть гп — максимальное из всех полученных таким образом количеств ребер. Предложите простое изменение алгоритма Ве~.мам Роко, позволяющее ему завершаться после выполнения т + 1 проходов, даже если т заранее неизвестно. 24.1-4. Модифицируйте алгоритм Вкы.мА ~ Роко таким образом, чтобы значения — со в нем присваивались атрибутам г( 1и) всех вершин е, для которых на одном из путей от истока к е имеется цикл с отрицательным весом.
* 24.1-5. Пусть О = (Ъ', Е) — взвешенный ориентированный граф с весовой функцией и: Е В.. Разработайте алгоритм со временем работы ОЯЕ), который позволял бы для каждой вершины исЪ' найти величину 6' (с) = = ш1п„аь (с(и,с)). *24.1-6. Предположим, что взвешенный ориентированный граф С = (1г, Е) содержит цикл с отрицательным весом.
Разработайте эффективный алгоритм, позволяющий вывести список вершин одного такого цикла. Докажите, что предложенный вами алгоритм корректен. Глава 24. Кратчайшие пути из одной вершины 677 24.2 Кратчайшие пути из одной вершины в ориентированных ациклических графах Ослабляя ребра взвешенного ориентированного ациклического графа С = = (1', Е) в порядке, определенном топологической сортировюй его вершин, кратчайшие пути из одной вершины можно найти в течение времени О (Ъ' + Е).
В ориентированном ацикличесюм графе кратчайшие пути всегда вполне определены, поскольку даже если у некоторых ребер вес отрицателен, циклов с отрицательными весами не существует. Работа алгоритма начинается с топологичесюй сортировки ориентированного ацикличесюго графа (см. раздел 22.4), чтобы установить линейное упорядочение вершин. Если путь из вершины и к вершине в существует, то в топологичесюй сортировке вершина и предшествует вершине ю. По вершинам, расположенным в топологичесюм порядке, проход выполняется только один раз. При обработке каждой вершины производится ослабление всех ребер, исходящих из этой вершины. 1ЭАО ЯНОКТЕБТ РАТНЗ(С, и, а) 1 Топологическая сортировка вершин графа С 2 1141Т1АЫЕЕ Я!Н01.Е 801ЖСЕ(С, а) 3 1ог (для) каждой вершины и в порядке топологической сортировки 4 ео $ог (Для) каждой вершины о Е Аф[и] 5 Йо неьАх(и) с, 1л) Работа этого алгоритма проиллюстрирована на рис.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
