Т. Кормен, Ч. Лейсерзон, Р. Риверст, К. Штайн - Алгоритмы. Построение и анализ (2013) (1162189), страница 152
Текст из файла (страница 152)
И = оь. Н = б(в, сь) = б(в, о). Следствие 24.3 Пусть С = ($', Е) является взвешенным ориентированным графом с истоком в и весовой функцией ш: Š— ~ К и пусть граф С ие содержит достижимых из в циклов с отрицательным весом. Тогда для каждой вершины о б 'ьг путь из вершины в в вершину о существует тогда и только тогда, когда после применения к графу С процедуры ВееемАм-Ропп выполняется неравенство о. 4 < сс.
Доказательство. Доказательство этого следствия остается читателю в качестве упр. 24.1.2. Теорема 24.4 (Корректность алгоритма Беллмена-Форда) Пусть алгоритм ВееемАМ-РОкп применяется к взвешенному ориентированному графу С = (1г, Е) с истоком в и весовой функцией ю; Е + К. Если граф С не содержит циклов с отрицательным весом, достижимых из вершины в, то этот алгоритм возвращает значение ткце, для всех вершин о Е )г выполняется равенство щ И = б(в, о) и подграф предшествования С, является деревом кратчайших путей с корнем в вершине в. Если же граф С содержит цикл с отрицательным весом, достижимый из вершины в, то алгоритм возвращает значение ГАьзе. Догсазательство. Предположим, что граф С не содержит циклов с отрицательным весом, достижимых из истока ж Сначала докажем, что по завершении работы алгоритма для всех вершин о е )г выполняется равенство о.
4 = б(в, и). Если вершина о достижима из истока в, то доказательством этого утверждения служит глава 24 Кратчайшие пути из одной вершимы и.11 = Ю(в,и) < д(в, и) + ю(и, и) = и.н+ и1(и,и), (согласно неравенству треугольника) так что ни одна из проверок, выполненных в строке 6, не приведет к тому, что алгоритм Вееемл1ч-Гоко возвратит значение елезе. Следовательно, ему ничего не остается, как возвратить значение тКОЕ.
Теперь предположим, что граф 0 содержит цикл с отрицательным весом, достижимый из истока в; пусть это будет цикл с = (ио, и1,..., иь), где ис = иь. Тогда и~(и, 1,и1) < О . (24.1) Чтобы воспользоваться методом "от противного", предположим, что алгоритм Внл.мл1ч-роно возвращает значение ткое. Тогда для значений 1 = 1,2,..., 14 выполняются неравенства ио 1( < ич 1. в(+ зо(и, 1, ив). Просуммировав их по все- му циклу с, получим ь ь ~Ги1.11 < ~(и1 1.11+ и(и1 1,и1)) 1=1 1=1 ь ь ~и1-1 ° и + Х~~ и'(и1-1~ и1) Поскольку ис = иы каждая вершина в цикле с в каждой сумме 2', 1и1.1( и '>„1 1 и; 1. 1( появляется ровно по одному разу, так что ь Кроме того, согласно следствию 24.3 атрибут и1. Ы при 1 = 1, 2,..., 14 принимает конечные значения.
Таким образом, справедливо неравенство ь О < ~~~ чв(и; 1,и1), 1=1 лемма 24.2. Если же вершина и не достижима из вершины в, то это утверждение следует нз свойства отсутствия пути. Таким образом, данное утверждение доказано. Из свойства подграфа предшествования и этого утверждения следует, что граф С, — дерево кратчайших путей. А теперь с помощью обоснованного выше утверждения покажем, что алгоритм Вееемхм-Гоко возвращает значение тите. По завершении работы алгоритма для всех ребер (и, и) Е Е выполняется соотно- шение Часть Р1.
Алгоритмы для работы с графами 692 что противоречит неравенству (24.1). Итак, мы приходим к выводу, что алгоритм ВееемАм-Ропп возвращает значение ткие, если граф С не содержит циклов с отрицательным весом, достижимых из истока, и значение ГАЕБŠ— в противном случае. Упражнения 24.1.1 Примените алгоритм ВееемАн-Ропп к ориентированному графу, показанному на рис. 24.4, в котором в качестве истока используется вершина г.
В процессе каждого прохода ослабление ребер должно выполняться в том же порядке, что и на рисунке. Составьте список значений, которые принимают атрибуты Ы и я после кюкдого прохода. А теперь измените вес ребра (г, х), присвоив ему значение 4, и выполните алгоритм снова, используя в качестве истока вершину а. 24.1.2 Докажите следствие 24.3. 24.1.3 Пусть дан взвешенный ориентированный граф С = (й; Е), который не содержит циклов с отрицательным весом.
Для каждой пары вершин и, с Е $' найдем минимальное количество ребер в кратчайшем пути от с к и (длина пути определяется его весом, а не количеством ребер). Пусть т — максимальное из всех полученных таким образом количеств ребер. Предложите простое изменение алгоритма ВеьемАМ-РОкп, позволяющее ему завершаться после выполнения т+1 проходов, даже если т заранее неизвестно. 241.4 Модифнцируйте алгоритм ВееемАн-Рокй таким образом, чтобы в нем для всех вершин с, для которых на одном из путей от истока к и имеется цикл с отрицательным весом, атрибутам щ 4 присваивались значения — оэ.
24.1.5 * Пусть С = ()г, Е) — взвешенный ориентированный граф с весовой функцией щ: Š— > К. Разработайте алгоритм со временем работы ОЯЕ), который позволял бы для каждой вершины о Е Ъ' находить величину 6*(с) = ппп е~ 1о(и, о)). 24.1.б * Предположим, что взвешенный ориентированный граф С = (Ъ;Е) содержит цикл с отрицательным весом. Разработайте эффективный алгоритм, позволяющий вывести список вершин одного такого цикла.
Докажите, что предложенный вами алгоритм корректен. б93 Глава 24 Кратчайшие вути ил одиой вершииы 24.2. Кратчайшие пути из одной вершины в ориентированных апиклических графах Оспабпяя ребра взвешенного ориентированного ацикпического графа С = ()Г, Е) в порядке, определенном топологической сортировкой его вершин, кратчайшие пути из одной вершины можно найти за время еэ(Ъ'+ Е). В ориентированном ацикпическом графе кратчайшие пути всегда вполне определены, поскольку, даже если вес некоторых ребер отрицателен, циклов с отрицательными весами не существует.
Работа алгоритма начинается с топологической сортировки ориентированного ацикпического графа (см. раздел 22.4), которая должна установить линейное упорядочение вершин. Если путь из вершины и к вершине и существует, то в топологической сортировке вершина и предшествует вершине м По вершинам, расположенным в топопогическом порядке, проход выполняется только один раз. При обработке каждой вершины производится ослабление всех ребер, исходящих из этой вершины.
РАО-БНОКТЕЗТ-РАТНЗ(С, чо, в) 1 Топологическая сортировка вершин графа С 2 1штиыхе-Бпйсее-БООксе(С, в) 3 Гог каждой вершины и в порядке топологической сортировки 4 Гог каждой вершины и Е С. Абй [и] 5 КЕЕАХ(и, и, и) Работа этого апгоритма проиллюстрирована на рис. 24.5. Время работы этого алгоритма легко проанализировать. Как показано в раздепе 22.4, топопогическая сортировка в строке 1 выполняется за время чэ(Ъ'+ Е). Вызов процедуры 1шт|Аыее-Бпчпее-БООксе в строке 2 занимает время еэ()л). На каждую вершину приходится по одной итерации цикла Гог в строках 3 — 5. Цикл Гог в строках 4 и 5 ослабляет каждое ребро по одному разу (мы используем здесь групповой анализ).
Поскольку каждая итерация внутреннего цикла Гог занимает время Й(1), полное время работы апгоритма равно Й(Ъ'+ Е), т.е. линейно зависит от размера представления графа с использованием списков смежности. Из сформулированной далее теоремы видно, что процедура 13АО-БнОктезтРАтнз корректно вычисляет кратчайшие пути. Теорема 24.5 Если взвешенный ориентированный граф С = (1~, Е) имеет исток а и не содержит циклов, то по завершении процедуры ПАО-Бноктезт-РАтнз для всех вершин и е 1л выполняется равенство и. д = б(а, и), а подграф предшествования С представляет собой дерево кратчайших путей. Доказаавельеввео.
Сначала покажем, что по завершении процедуры дпя всех вершин и е К выполняется равенство и. Ы = б(в,и). Если вершина и недостижима из истока в, то согласно свойству отсутствия пути выполняется соотноше- Часть РГ. Алгоритмы длл работы с графами б94 б (в) (6) Ф' (в) г (й(р "-- (в) (м) Рис. 24.5. Работа алгоритма поиска кратчайших путей в ориеитироваииом ацикличесюм графе. Вершины топологически отсортироваиы слева направо. Истоком являетса вершина ж В вершииах указаны зиачеиия атрибута г(, а ребра указывают значения к. (а) Ситуация перед первой итерацией цикла Гог в строках 3 — 5. (б)-(ж) Ситуация после кшкдой итерации цикла Рог в строках 3-5.
Вновь звчериеииая иа очерелиой итерации вершина используется в качестве вершины и. Значения, показаииые в части (ж), явлтотся окончательными. ние ю. (( = 6(л, о) = со. Теперь предположим, что вершина и достижима из истока л, а следовательно, существует кратчайший путь р = (оо, и),...,ил), где оо = л, а еь = е. Посксльку вершины обрабатываются в порядке топологической сортировки, ребра пути р ослабляются в порядке (ио, и)), (о), из),..., (оь ), еь). Из свойства ослабления путей следует, что по завершении процедуры для всех ) = О, 1,..., )с выполняетси равенство ц(. (( = б(л, и(). И наконец согласно свойству подграфа предшествования С является деревом кратчайших путей. Интересное применение этого алгоритма возникает при определении критических путей во время анализа диаграммы РЕКТ (РЕ)ьТ с))а)т)2.
Ее ребра представляют предназначенные для выполнения задания, а вес каждого из ребер— промежутки времени, необходимые для выполнения того или иного задания. Ес- здббревиатура "РЕКГ' расшифровывается квк "ргоагвпг еаза)шбоп впб ген)ев мсьшг)ве" — спсшмв птвяв- роввкия и руководства рвзрвбопшмп. 695 Глана 24 Кратчайшие нута из одной вершины ли ребро (и, о) входит в вершину с, а ребро (с, х) покидает ее, это означает, что задание (и,с) должно быть выполнено до задания (с,х).
Путь по такому ориеитироваииому ациклическому графу представляет последовательность заданий, которые необходимо выполнить в определенном порядке. Критический вуаль (спбса1 раба) — самый длинный путь в ориентированном ациклическом графе, соответствующий самому длительному времени, необходимому для выполнения упорядочеииой последовательности заданий. Таким образом, вес критического пути предоставляет нижнюю границу полного времени выполнения всех задаиий. Критический путь можно найти одним из следующих двух способов: заменив знаки всех весов ребер и выполнив алгоритм РАс-Биоктезт-Рятнз; воспользовавшись модифицированным алгоритмом 0лп-бнокткзт-РАтнз, в котором в строке 2 процедуры 1ы1т~лщхп-Бпчоье-Яо15кси значение со замеиеио значением — со, а в процедуре Кн.лх знак ")" заменен знаком "<".
Упрвжиеиия 24.2Л Выполните процедуру РАп-Яноктязт-Рлтнз для графа, показанного иа рис. 24.5, с вершиной т в качестве истока. 24.г.г Предположим, что строка 3 в процедуре 13яс-Бнокткзт-Рлтнз изменена следующим образом: 3 1ег первых ~Ц вЂ” 1 вершин в порядке топологической сортировки Покажите, что процедура останется корректной. 24.2.З Представленное выше описание диаграммы РБКТ несколько неестественно. Естествеииее было бы, если бы вершины представляли задания, а ребра — ограиичеиия„иакладываемые иа порядок их выполнения, т.е. если бы иаличие ребра (и, о) указывало иа то, что задание и необходимо выполнить до задания с.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
