Т. Кормен, Ч. Лейсерзон, Р. Риверст, К. Штайн - Алгоритмы. Построение и анализ (2013) (1162189), страница 163
Текст из файла (страница 163)
Чем матрица Ф похожа на таблицу з, которая используется в задаче о перемножении цепочки матриц из раздела 15.2? 25.2.а Разработайте алгоритм, позволяющий вычислить транзитивное замыкание ориентированного графа С = (Ъг, Е) за время 0(Ъ'Е). 25.2.9 Предположим, что транзитивное замыкание ориентированного ациклического графа можно вычислить за время 7(~Ц, )Е~), где 7" — монотонно возрастающая функция от Щ и ))Е). Покажите, что в таюм случае время поиска транзитивного замыкания С* = (Ъг, Е*) ориентированного графа общего вида С = (Ъ; Е) равно 2(~Ъг~, (Е~) + 0(Ъ'+ Е'). 25.3. Алгоритм Джонсона для разреженных графов Алгоритм Джонсона позволяет найти кратчайшие пути между всеми парами вершин за время 0(Ъ'з 1я Ъ'+ Ъ'Е).
Для разреженных графов в асимптотическом пределе он ведет себя лучше, чем алгоритм многократного возведения матриц в квадрат и алгоритм Флойда — Уоршелла. Этот алгоритм либо возвращает матрицу, содержащую веса кратчайших путей для всех пар вершин, либо выволгг: сообшение о том, что входной граф содержит цикл с отрицательным весом. В ат- Глава 75. Крашчвашве луши между всеми сарами вершин 739 горитме Джонсона используются подпрограммы, в которых реализованы алгоритмы Дейкстры и Беллмана-Форда, описанные в главе 24.
В алгоритме Джонсона используется метод изменения веса (гезве)йЫпй), работающий следующим образом. Если веса всех ребер и в графе С = ()7, Е) неотрицательны, можно найти кратчайшие пути между всеми парами вершин, по разу запустив алгоритм Дейкстры для каждой вершины. Если неубывающая очередь с приоритетами реализована в виде пирамиды Фибоначчи, то время работы такого алгоритма будет равно 0()лз 1к Ъ' + )7Е). Если же в графе С содержатся ребра с отрицательным весом, но отсутствуют циклы с отрицательным весом, можно вычислить новое множество неотрицательных весов ребер, позволяющее воспользоваться тем же методом.
Новое множество весов ребер и должно удовлетворять двум важным свойствам. 1. Для всех пар вершин и, и Е 17 путь р является кратчайшим путем из вершины и в вершину и с использованием весовой функции и тогда и только тогда, когда р является также кратчайшим путем из вершины и в вершину и с весовой функцией ю. 2.
Для всех ребер (и,и) новый вес зс(и,и) неотрицателен. Как мы вскоре увидим, предварительную обработку графа С с целью определить новую весовую функцию во можно выполнить за время 0(Ъ'Е). Сохранение кратчайших путей Приведенная ниже лемма показывает, как легко организовать изменение весов, удовлетворяющее первому из сформулированных выше свойств. Значения весов кратчайших путей, полученные с помощью весовой функции ю, обозначены как Ю, а веса кратчайших путей, полученных с помощью весовой функции во,— как Х Лемма 25Л (Изменение весов сохраняет кратчайшие пути) Пусть для заданного взвешенного ориентированного графа С = (17, Е) с весовой функцией во: Е -э 1й функция Ь: К -з К вЂ” произвольная функция, отображающая вершины на действительные числа. Для каждого ребра (и, и) Е Е определим й(и, и) = во(и, и) + Ь(и) — 6(и) .
(25.9) Пусть р = (ио, иы..., и») — произвольный путь из вершины ио в вершину и». Путь р является кратчайшим путем с весовой функцией вл тогда и только тогда, когда он является кратчайшим путем с весовой функцией ю„т.е. равенство во(р) = б(ио, и») равносильно равенству во(р) = 6(ие, и»). Кроме того, граф С содержит цикл с отрицательным весом при использовании весовой функции и тогда и только тогда, когда он содержит цикл с отрицательным весом при использовании весовой функции й» Доказательство.
Сначала покажем, что (25.10) Части 'гх Алгоритмы для работы с графами Мы имеем ю(р) = ~~1 ю(,,и;) 1=1 й (ю(и; 1, и1) + Ь(и1 1) — Ь(и,)) 1=1 ь = ~~~. ю(и -м и ) + Ь(ио) — Ь(иь) ми 1 = ю(р) + Ь(ио) — Ь(иь) . (в силу телескопичности суммы) Следовательно, для любого пути р нз вершины ио в вершину иь справедливо соотношение ю(р) = 10(р) + Ь(ис) — Ь(иь). Поскольку Ь(ис) и Ь(иь) не зависят от пути, то если один путь из ио в иь короче другого при использовании весовой функции ю, то он будет короче и при использовании весовой функции ю. Таким образом, ю(р) = б(ио, иь) тогда и только тогда, когда ю(р) = 6(ио, иь).
Наконец покажем, что 1раф С имеет цикл с отрицательным весом с использованием весовой функции ю тогда и только тогда, когда он имеет такой цикл с использованием весовой функции ю. Рассмотрим произвольный цикл с = (ис, и1,..., иь), где ио = иь. В соответствии с уравнением (25.10) выполняется соот- ношение ю(с) = ю(с) + Ь(ио) — Ь(иь) = ю(с), а следовательно, вес цикла с будет отрицательным с использованием весовой функции ю тогда и только тогда, когда он отрицательный с использованием весо- вой функции ю.
Генерация неотрицательных весов путем их изменения Следующая наша цель — обеспечить выполнение второго свойства: нужно, чтобы величина ю(и, и) была неотрицательной для всех ребер (и, и) Е Е. Для данного взвешенного ориентированного графа С = (Ъ; Е) с весовой функцией ю: Е -4 )й мы создадим новый граф С' = (11', Е'), где ви = Ъ' О (л) для некоторой новой вершины а ф 1г и Е' = Е О ((л, и): и Е )г).
Расширим весовую функцию ю таким образом, чтобы для всех вершин и е Ъ' выполнялось равенство ю(л, и) = О. Заметим, что поскольку в вершину а не входит ни одно ребро, зту вершину не содержит ни один кратчайший путь графа С', отличный от того, который исходит из а. Кроме того, граф С' не содержит циклов с отрицательным весом тогда и только тогда, когда таких циклов не содержит граф С. На рис.
25.6, (а) показан граф С', соответствующий графу С на рис. 25.1. Теперь предположим, что графы С и С' не содержат циклов с отрицательным весом. Определим для всех вершин и е Ъ" величину Ь(и) = б(л,и). Согласно Лглеа 25. Кра(ячайшие луши мезсду ясами лгриьии вершин 74) .." 0 2 0 5 ш) (в) ,2))„ю вй)0) 00 (в) 5 4 (в) 5 4 5 4 (в) (и! Рис. 25.6. Работа авгоритма Длшнсонж предназначенного длл поиска кратчайших путей между всеми парами вершин, с графом, иэабрюкенным на рис.25.1.
(а) Гриф С' с исходной весовой фующией ш. Новая вершина е указана черным цвегом. В каждой вершине с показано значение ))(о) = 6(е, о). (6) После изменения веса ишщого ребра (и, о) с использованием весовой функции ю(и, с) = ви(и, о) + ))(и) — ))(о). (иКж) Рез)пьтат применения алгоритма Дейзмтры для каждой вершины С с использованием весовой функцин ви. В квкдой части источник и указан черным цветом, а звштрнховмпяые ребра образуют дерево кратчайших путей, вычисленное алгоритмом. В каждой вершине о повшаны значения б(и,и) и 6(и, о), разделенные косой чертой.
Значение в( „= 6(и, с) равно б(и, о) + ))(и) — Ци). Часть 17. Аггоритмы ам работы с графами 742 неравенству треугольника (лемма 24.10) для всех ребер (и, с) е Е' выполняется соотношение Ь(с) < Ь(и) + ю(и, с). Таким образом, если мы определим новые веса ю в соответствии с уравнением (25.9), то получим ю(и, с) = ю(и, о) + Ь(и) — Ь(с) > О, так что второе свойство удовлетворяется.
На рис. 25.6, (б) показан граф С', полученный в результате переопределения весов ребер графа, изображенного на рис. 25.6, (а). 3оннзон(С,ю) ! Вычислить С', где С'. Р = С. (7 12 (а), С'. Е = С. Е ~2 ((з, с): с Е С. 17), и ю(з,с) = 0 для всех и е С. 17 2 11 Ве1л.мАх-ГОкй(С', ю, з) == ЕАйБе 3 рпп1 "входной граф содержит цикл с отрицательным весом" 4 е1зе Гог каждой вершины и Е С'. Р 5 установить Ь(и) равным значению б(а, и), вычисленному алгоритмом Беллмана-Форда 6 1ог каждого ребра (и,с) е С'. Е 7 ю(и,с) = ю(и, и) + Ь(и) — Ь(77) 8 Пусть Р = (с(иь) — новая матрица размером и х и 9 Гог каждой вершины и Е С.
1' 10 выполнить РыкзткА(С, ю, и) для вычисления б(и, с) для всех и е С. )г 1ог каждой вершины с Е С. 17 с(„„= б(и, и) + Ь(с) — Ь(и) гехцгп Р 11 12 13 В этом коде просто выполняются описанные ранее действия. В строке 1 строится граф С'. В строке 2 выполняется алгоритм Беллмана — Форда с входным графом С', весовой функцией ю и истоком ж Если граф С', а следовательно и граф С, содержат цикл с отрицательным весом, об этом выводится сообщение в строке 3. В строках 4-12 предполагается, что граф С' не содержит циклов с отрицательным весом.
В строках 4 и 5 для всех вершин с Е 17' величине Ь(с) присваивается вес кратчайшего пути б(а, и), вычисленный алгоритмом Беллмана — Форда. В строках 6 и 7 для каждого ребра вычисляется новый вес ю. Для каждой пары Вычисление кратчайших путей между всеми парами вершин В алгоритме Джонсона, предназначенном для вычисления кратчайших путей между всеми парами вершин, в качестве подпрограмм используются алгоритм Беллмана-Форда (раэдел 24.1) и алгоритм Дейкстры (раздел 24.3).
Предполагается, что ребра хранятся в виде списков смежных вершин. Этот алгоритм возвращает обычную матрицу Р = бб размером )Ъ'~ х Щ, где с(ч — — б(1,2), или выдает сообщение о том, что входной граф содержит цикл с отрицательным весом. Предполагается, что вершины пронумерованы от 1 до Щ, что типично для алгоритмов, предназначенных для поиска кратчайших путей между всеми парами вершин.
Глава 25. Кратчайшие лути между всеми ларами вершин 145 вершин и, о Е К цикл аког в строках 9-12 вычисляет вес кратчайшего пути ю(и, и) с помощью однократного вызова алгоритма Дейкстры для каждой вершины из множества К, В строке 12 в элемент матрицы с(„„заносится корректный вес кратчайшего пути б(п, о), вычисленный с помощью уравнения (25.10).
Наконец в строке 13 возвращается вычисленная матрица .О. Работа алгоритма Джонсона проиллюстрирована на рис. 25.6. Если неубывающая очередь с приоритетами реализована в алгоритме Дейкстры в виде пирамиды Фибоначчи, то время работы алгоритма Джонсона равно 0(112 1я К + Ъ Е). Более простая реализация неубывающей очереди с приоритетами приводит к тому, что время работы становится равным 0(Ъ'Е 1йЪ'), но для разреженных графов зта величина в асимптотическом пределе ведет себя лучше, чем время работы алгоритма Флойда — Уоршелла.
Упражнения 25.3.1 Вычислите с помощью алгоритма Джонсона кратчайшие пути между всеми парами вершин в графе, изображенном на рис.25.2. Приведите значения 6 и ю, вычисленные этим алгоритмом. 25.3.2 Зачем в множество 11 добавляется новая вершина в, в результате чего создается множество $"? 25.3.3 Предположим, что для всех ребер (и, п) Е Е выполняется неравенство ю(и, и) > О. Как между собой взаимосвязаны весовые функции ш и ю? 25.3.4 Профессор утверждает, что изменить веса ребер можно проще, чем это делается в алгоритме Джонсона.
Полагая ю* = ш1п(ш„1еи (ю(п,п)), просто определим ю(и,п) = ю(п,о) — ю' для всех ребер (и,п) е Е. Где кроется ошибка в методе, предложенном профессором? Предположим, что алгоритм Джонсона выполняется для ориентированного графа С с весовой функцией ю. Покажите, что если граф С содержит цикл с с нулевым весом, то для всех ребер (и, с) этого цикла ю(и, е) = О.
25.3. б Профессор утверждает, что нет необходимости создавать новую вершину-исток в строке 1 алгоритма 1ОннзОн. Профессор считает, что вместо этого можно использовать С' = С, а в роли вершины в использовать произвольную вершину. Приведите пример взвешенного ориентированного графа С, для которого воплощение идеи профессора в алгоритме 1ОнхзОН даст неправильный ответ. Затем покажите, что если граф С сильно связный (каждая его вершина достижима из Часть И. Аагоратмы дла работы с графами любой другой вершины), то результаты работы алгоритма 3оннзон, модифици- рованного профессором, будут верны.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
