Т. Кормен, Ч. Лейсерзон, Р. Риверст, К. Штайн - Алгоритмы. Построение и анализ (2013) (1162189), страница 159

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 159)

Докажите, что для ю' = 2, 3,..., к и всех о е Ъ' бг(в, о) = б;(в, о) + 26, 1(в, о) и что 6,(в, о) < (Е1 е, Покажите, как вычислить 6,(в, о) из б, г (в, о) для всех о Е 17 за время 0(Е), и сделайте вывод о том, что можно вычислить 6(в,о) для всех о е $' за время 0(Е 1я И'). 24.5. йиорнтм Карпа для канска цикла с мнннмальнавм средним весам Пусть С = (17, Е) представляет собой ориентированный граф с весовой функцией ш: е -+ к и пусть и = (Ц.

Определим среднай вес (шеал лкещьг) цикла с = (еы ез,..., еь), состоящего из ребер множества Е, как ь 7л(с) = — ~~ ш(е;) . в=г Пусть !л' = ппп,7л(с), где с охватывает все ориентированные циклы графа С. Цикл с, для которого выполняется равенство !л(с) = р', называется циклам с минимальным средним весам (пшшпшп шеап-юе(ййГ сус!е). В этой задаче исследуется зффективный алгоритм вычисления величины р'.

Без потери общности предположим, что каждая вершина о й Ъ' достижима из истока в Е Ъ'. Пусть 6(в,о) — вес кратчайшего пути из истока в в вершину о, а бь(в, о) — вес кратчайшего пути из истока в в вершину о, содержащего ровно !о ребер. Если такого пути не существует, то бь(в,о) = оо. ж Покажите, что если 7л' = О, то граф С не содержит циклов с отрицательным весом и 6(в, о) = пипа<ай„ г бь(в, о) для всех вершин о е Ъ'.

720 Часть р!. Алгорытмы длл работы с графами б. Покажите, что если 7л* = О, то б„(в, гг) — бь(в, о) щах >0 ойь< -1 п — й для всех вершин и Е У. (Указание; воспользуйтесь обоими свойствами из п. (а).) в. Пусть с — цикл с нулевым весом, а и и 0 — две произвольные вершины в этом цикле. Предположим, что 7л' = 0 и что вес пути из вершины и в вершину с вдоль цикла равен х.

Докажите, что б(в, о) = б(в, и) + х. (Указание: вес простого пути из вершины о в вершину и вдоль цикла равен — х.) а Покажите, что если 7л' = О, то в каждом цикле с минимальным средним весом существует вершина с, такая, что б„(в,с) - бь(в,о) щах о«я< -з п — й (Указание: покажите, как можно расширить кратчайший путь в каждую вершину, принадлежацую циклу с минимальным средним весом, вдоль цикла, чтобы получить путь к следующей вершине цикла.) д.

Покажите, что если 1л' = О, то б„(в, с) — бь(в, с) пип шах тали 0<ьйо-1 и — й е. Покажите, что если к весу каждого ребра графа С добавить константу г, то величина 7г' увеличится на Е Покажите с помощью этого факта справедливость соотношения б„(в, о) — бь(в, 0) 7л' = ппп щах ьб1' Ойьйо-1 и — й ж. Разработайте алгоритм, позволяющий вычислить величину 1л' за время 0(УЕ). 24.б. Ботанические кратчайшие нути Последовательность называется баталической (Ьйоп(с), если она монотонно возрастает, а затем монотонно убывает, или если путем циклического сдвига ее можно привести к такому виду.

Например, битоническими являются последовательности (1,4,6,8,3, — 2), (9,2, — 4, — 10, — 3) и (1,2,3,4), но не (1,3,12,4,2,10). (См. битоническую евклидову задачу о коммивояжере 15.3.) Предположим, что задан ориентированный граф С = (У, Е) с весовой функцией ю: Е -+ )к и нужно найти кратчайшие пути из одной вершины в. Имеется также дополнительная информация: для каждой вершины с е У веса ребер вдоль любого кратчайшего пути из истока в в вершину с образуют битоническую последовательность. Гзава 24. Кратчайшие нута из одной вершины Разработайте наиболее эффективный алгоритм, позволяющий решить эту задачу, и проанализируйте время его работы.

Заключительные замечания Алгоритм Дейкстры Щ1свпа) [87) был разработан в 1959 году, но в нем не содержалось никаких упоминаний об очереди с приоритетами. Алгоритм БеллманаФорда основан на отдельных алгоритмах Беллмана (Ве!Ьпап) [37) и Форда (Рогб) [108]. Беллман указал, как кратчайшие пути связаны с разностными ограничениями.

Лоулер (Еачи!ег) [223] описал алгоритм с линейным временем работы для поиска кратчайших путей в ориентированном ациклическом графе, который он рассматривает как часть "народного творчества". Если вес каждого из ребер выражается сравнительно малыми неотрицательными целыми числами, задача о кратчайших путях из одной вершины решается с помощью более эффективных алгоритмов. Последовательность значений, возврашаемых в результате вызовов процедуры Ехтклст-Мпя в алгоритме Дейкстры, монотонно возрастает со временем.

Как говорилось в заключительных замечаниях к главе 6, в этом случае существует несколько структур данных, позволяющих эффективнее реализовать различные операции над очередями с приоритетами, чем бинарная пирамида или пирамида Фибоначчи. Ахуя (АЬща), Мельхорн (МеЬ)Ьогп), Орлин (Ог![п) и Таржан (Таганки) [8) предложили для графов с неотрицательными весами ребер алгоритм со временем работы 0(Е + $';48 И"), где И' — максимальный вес ребра графа. Наилучшие границы достигнуты Торупом (ТЬогпр) [335), который предложил алгоритм со временем работы 0(Е 18 18 И), и Раманом (Кшпап) [289), алгоритм которого имеет время работы 0 (Е+ Ъ'ппп 1(18 $')г~з+', (18 И')4~4+')). Оба алгоритма используют объем памяти, зависящий от размера слова машины, на юторой выполняется алгоритм. Хотя объем используемой памяти может оказаться неограниченным в зависимости от размера входных данных, с помощью рандомизированного хеширования его можно снизить до линейно зависяшего от размера входных данных.

Для неориентированных графов с целочисленными весами Торуп [334) привел алгоритм со временем работы 0(И+ Е), предназначенный для поиска кратчайших путей из одной вершины. В отличие от алгоритмов, упомянутых в предыдушем абзаце, этот алгоритм — не реализация алгоритма Дейкстры, посюльку последовательность значений, возврашаемых вызовами процедуры Ехтклст-М4т, не является монотонно неубывающей.

Для графов, содержащих ребра с отрицательными весами, алгоритм, предложенный Габовым (ОаЪочч) и Таржаном [121), имеет время работы О( ЯЕ 18(Ъ'Я)), а предложенный Гольдбергом (Оо!бЬег8) [136) выполняется за время 0(ч"йЕ 18 И'), где И' = шах( „1е и. (/ю(п, с) !). Черкасский (СЬег)саззйу), Гольдберг (ОоЫЬегй) и Радзик (Ка<Ыс) [63) провели большое количество экспериментов по сравнению различных алгоритмов, предназначенных для поиска кратчайших путей. Глава 25. Кратчайшие пути между всеми парами вершин В этой главе рассматривается задача о поиске кратчайших путей между всеми парами вершин графа. Эта задача может возникнуть, например, прн составлении таблицы расстояний между всеми парами городов, нанесенных на атлас дорог. Как и в главе 24, в этой задаче задается взвешенный ориентированный граф С = (Ъ; Е) с весовой функцией ш: Е -э м, отображающей ребра на их веса, выраженные действительными числами.

Для каждой пары вершин и, и е Ъ требуется найти кратчайший (обпадающий наименьшим весом) путь из вершины и в вершину о, вес которого определяется как сумма весов входящих в него ребер. Обычно выходные данные представляются в табличной форме: на пересечении строки с индексом и и столбца с индексом о расположен вес кратчайшего пути из вершины и в вершину ю. Задачу о поиске кратчайших путей между всеми парами вершин можно решить, выполнив ~Ъ'~ раз алгоритм поиска кратчайших путей из одной вершины, каждый раз выбирая в качестве истока новую вершину графа.

Если веса всех ребер неотрицательные, можно воспользоваться алгоритмом Дейкстры. Если используется реализация неубывающей очереди с приоритетами в виде линейного массива, то время работы такого алгоритма равно 0(Ъ'з + Ъ'Е) = О(Ъ'з). Если же неубывающая очередь с приоритетами реализована в виде бинарной неубывающей пирамиды, то время работы будет равно 0(Ъ'Е)кЪ'), что предпочтительнее для разреженных графов, Можно также реализовать неубывающую очередь с приоритетами с помощью пирамиды Фибоначчи; в этом случае время работы алгоритма равно 0(Ъ'з 1я Ъ' + 1'Е). Если в графе могут быть ребра с отрицательным весом, алгоритм Дейкстры неприменим.

Вместо него для каждой вершины следует выполнить более медленный алгоритм Беллмана — Форда. Полученное в результате время работы равно 0(Ъ'зЕ), что для плотных графов можно записать как 0(Ъ'4). После чтения этой главы станет понятно, как лучше поступить в том или ином случае. Будет также исследована связь задачи о кратчайших расстояниях между всеми парами вершин с умножением матриц и изучена алгебраическая структура этой задачи. В отличие от алгоритмов поиска кратчайшего пути из фиксированного истока, в которых предполагается, что представление графа имеет вид списка смежных вершин, в большинстве представленных в этой главе алгоритмов используется представление в виде матрицы смежности.

(В алгоритме Джонсона (УоЬпзоп) для разреженных графов в разделе 25.3 используются списки смежности.) Для удоб- Глава г5. А)вамчайшив луши между всеми ларами вершин ггз ства предполагается, что вершины пронумерованы как 1, 2,..., ~ Ъ'~, поэтому в ро- ли входных данных выступает матрица И' размером и х п, представляющая веса ориентированных ребер (дуг) ориентированного графа С = ((г, Е) с и вершина- ми. Другими словами, И' = (пг, ), где О, если г = г, пгп — — вес дуги (г, г), если г ф 1 и (1,5) б Е, со, если 1 ф 1 и (1, г) 1с Е . (25.1) ггвд = (г Н (Г: ггц ~ Хн.) 0 (1) и Е; = ((Ям,г'): г б Тгвв — (1)) Если С; является деревом кратчайших путей, то приведенная ниже процедура, представляющая собой модифицированную версию описанной в главе 22 проце- дуры Ркгнт-РАтн, выводит кратчайший путь из вершины г в вершину г.

Рк!гчт-АЫ.-РА!кЯ-БнОктезт-РАтн(П,1, г) 1 !11==5 2 рпп1 г 3 е1зеЫя;, == нп. 4 рппг '"Пути из" г' "в" г "не существует" 5 е1зе Ркгнт-Ап.-РА1кз-бноктезт-РАтн(П,1, гг;,) 6 рпп1 г' Наличие ребер с отрицательным весом допускается, но пока что предполагается, что входной граф не содержит циклов с отрицательным весом. Выходные данные представленных в этой главе алгоритмов, предназначенных для поиска кратчайших путей между всеми парами вершин, имеют вид матрицы Р = (г)г ) размером и х п, где элемент дг содержит вес кратчайшего пути из вершины з в вершину 51 Другими словами, если обозначить через б(г', г) кратчайший путь из вершины 1 в вершину г (как это было сделано в главе 24), то по завершении работы алгоритма г(ц — — б(1, г).

Характеристики

Список файлов книги