Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн - Алгоритмы - Построение и анализ (2 изд.) (1123758), страница 139
Текст из файла (страница 139)
В частях б-д проиллюстрирована ситуация после каждого очередного прохода по ребрам. Значения атрибутов И и я, приведенные в части д, являются окончательными. Алгоритм Беллмана-Форда завершает свою работу в течение времени О ('и' Е), поскольку инициализация в строке 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л) Работа этого алгоритма проиллюстрирована на рис.
24.5. Вершины на рисунке топологически отсортированы слева направо. В роли истока выступает вершина ж В вершинах приведены значения атрибутов о, а выделенные ребра указывают значения я. В части а рисунка приведена ситуация перед первой итерацией цикла 1ог в строках 3-5. В каждой из частей б — ж рисунка показаны ситуации, складывающиеся после каждой итерации цикла аког в строках 3-5. Кюкцая новая черная вершина используется в соответствующей итерации в качестве и. В части ж приведены конечные значения. Время выполнения этого алгоритма легко поддается анализу. Как показано в разделе 22.4, топологическую сортировку в строке 1 можно выполнить в течение времени 9 (У+ Е). Вызов процедуры 1н1т1Аыуе 81нО1.е БО11ксе в строке 2 занимает время 9 (1').
На каждую вершину приходится по одной итерации цикла (ог в строках 3-5. Для каждой вершины все исходящие из нее ребра проверяются ровно по одному разу. Таким образом, всего выполняется ~Е1 итераций внутреннего цикла аког в строках 4-5 (мы воспользовались здесь групповым анализом). Поскольку каждая итерация внутреннего цикла аког занимает время О (1), полное Часть ЧЕ Алгоритмы для работы с графами 678 6 ( й / — 3 Рис. 24.5. Иллюстрация работы алгоритма, предназначенного для поиска кратчайших путей в ориентированном ацнкличсском графе время работы алгоритма равно О (У + Е), т.е. оно выражается линейной функцией от размера списка смежных вершин графа.
Из сформулированной ниже теоремы видно, что процедура ПАо Яноктезт РАтнз корректно вычисляет кратчайшие пути. Теорема 24.5. Если взвешенный ориентированный граф С = (К Е) содержит исток в и не содержит циклов, то по завершении процедуры РАп Бноктйзт РАтнз для всех вершин н Е Ъ' выполняется равенство г~ [о] = б (в, и) и подграф предшествования С„представляет собой дерево кратчайших путей.
Доказагиельсиво. Сначала покажем, что по завершении процедуры для всех вершин и е У выполняется равенство Н [и] = б (з, о). Если вершина и недостижима из истока а, то, согласно свойству отсутствия пути, выполняется соотношение с~ [о] = 6 (в, о) = оо. Теперь предположим, что вершина о достижима из истока а и, следовательно, существует кратчайший путь р = (по, о1,..., оь), где оо = = з, а нь = и. Поскольку вершины обрабатываются в порядке топологической Глава 24. Кратчайшие пути из одной вершины 679 сортировки, ребра пути р ослабляются в порядке (ггс,ггг), (иг, ия), ..., (иь н ггь). Из свойства ослабления путей следует, что по завершении процедуры для всех г = О, 1,,!с выполняется равенство Ы [тг;~ = б (я,тгг).
И наюнец, согласно свойству подграфа предшествования, С вЂ” дерево кратчайших путей. И Интересное применение этого алгоритма возникает при определении критических путей во время анализа диаграммы РЕК Т (РОТ с!гап)~. Ребра представляют предназначенные для выполнения задания, а вес каждого из ребер — промежутки времени, необходимые для выполнения того или иного задания. Если ребро (и, и) входит в вершину гг, а ребро (тг, х) покидает ее, это означает, что задание (гз, и) должно быть выполнено перед заданием (тг, х). Путь по такому ориентированному ациклическому графу представляет последовательность заданий, которые необходимо выполнить в определенном порядке. Критический иугиь (спйса! раг1т)— самый длинный путь по ориентированному ациклическому графу, соответствующий самому длительному времени, необходимому для выполнения упорядоченной последовательности заданий.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
