Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн - Алгоритмы - Построение и анализ (2 изд.) (1123758), страница 150
Текст из файла (страница 150)
25.6а. Вычисление кратчайших путей между всеми парами вершин В алгоритме Джонсона, предназначенном для вычисления кратчайших путей между всеми парами вершин, используется алгоритм Беллмана-Форда (раздел 24.1) и алгоритм Дейкстры (раздел 24.3), реализованные в виде подпрограмм.
Предполагается, что ребра хранятся в виде списков смежных вершин. Этот алгоритм возвращает обычную матрицу .0 = 4 размером )У! х Щ, где 4~ — — б (г, т), или выдает сообщение о том, что входной граф содержит цикл с отрицательным весом. Предполагается, что вершины пронумерованы от 1 до ~Ц„что типично для алгоритмов„предназначенных для поиска кратчайших путей между всеми парами вершин. Глава 25. Кратчайшие пути между всеми парами вершин 729 3онмзон(С) 1 Строится граф С', где Ъ'[С'] = 1'[С] 0 (а), Е[С'] = Е[С] 0 ((з,и): и Е У[С]) и ю(в,и) = 0 для всех и 61'[С] 2 11' Вн~~.мАн Рокр(С', ю, в) = гл~.зн 3 1йеп рйп1 "Входной граф содержит цикл с отрицательным весом" 4 е1ве 1ог (для) каждой вершины и Е 1'[С'] 5 по присвоить величине Ь(и) значение 6(а, и), вычисленное алгоритмом Беллмана-Форда 6 1ог (для) каждого ребра (и, о) е Е[С'] 7 оо ю(и, и) — ю(и, и) + Ь(и) — Ь(и) 8 1ог (для) каждой вершины и Е 'г'[С] 9 оо вычисление с помощью алгоритма Вцкзткл(С, ю, и) величин б(и, о) для всех вершин о е У[С] 1ог (для) каждой вершины и Е Ъ'[С] йо И „— д(и, и) + Ь(о) — Ь(и) гегцгп Р В этом коде просто выполняются описанные ранее действия.
В строке 1 строится граф С'. В строке 2 выполняется алгоритм Беллмана-Форда с входным графом С', весовой функцией ю и истоком в. Если граф С', а следовательно, и граф С содержит цикл с отрицательным весом, об этом выводится сообщение в строке 3. В строках 4-11 предполагается, что граф С' не содержит циклов с отрицательным весом. В строках 4-5 для всех вершин и е 1"' величине Ь (о) присваивается вес кратчайшего пути 6 (в, и), вычисленный алгоритмом Беллмана-Форда. В строках 6-7 для каждого ребра вычисляется новый вес ю. Для каждой пары вершин и, и е 1' цикл 1ог в строках 8-11 вычисляет вес кратчайшего пути ю (и, о) путем однократного вызова алгоритма Дейкстры для каждой вершины из множества $'.
В строке 11 в элемент матрицы с(„„заносится корректный вес кратчайшего пути 6 (и, о), вычисленный с помощью уравнения (25.10). Наконец, в строке 12 возвращается вычисленная матрица Р. Работа алгоритма Джонсона проиллюстрирована на рис. 25.6. Если неубывающая очередь с приоритетами реализована в алгоритме Дейкстры в виде пирамиды Фибоначчи, то время работы алгоритма Джонсона равно 0 (Уз 18 У + 1' Е).
Более простая реализация неубывающей очереди с приоритетами приводит к тому, что время работы становится равным О (У Е 18 Ъ'), но для разреженных графов эта величина в асимптотическом пределе ведет себя лучше, чем время работы алгоритма Флойда-Варшалла. 730 4 н з ы Рис. 25.6. Работа алгоритма Джонсона, предназначенного для поиска кратчайших путей между всеми парами вершин, с графом, изображенным на рнс.
25.1 Упражнения 25.3-1. Вычислите с помощью алгоритма Джонсона кратчайшие пути между всеми парами вершин в графе, изображенном на рис. 25.2. Приведите значения Ь и ш, вычисленные зтим алгоритмом. 25.3-2. Зачем в множество 11 добавляется новая вершина а, в результате чего создается множество г'? «о /; о Часть Ч1. Алгоритмы для работы с графами 731 Глава 25. Кратчайшие пути между всеми парами вершин 25.3-3.
Предположим, что для всех ребер (и, о) Е Е выполняется неравенство ю (и, о) > О. Как между собой взаимосвязаны весовые функции ю и ю? 25.3-4. Профессор утверждает, что изменить веса ребер можно проще, чем это делается в алгоритме Джонсона. Для этого надо найти ю' = ппп1„„1еЕ ~ю (и, о)) и для всех ребер (и, о) Е Е принять ю (и, о) = = ю (и,о) — ю'. Где кроется ошибка в методе, предложенном профессором? 25.3-5.
Предположим, что алгоритм Джонсона выполняется для ориентированного графа С с весовой функцией ю. Покажите, что если граф С содержит цикл с с нулевым весом, то для всех ребер (и, о) этого цикла ю(и,и) = О. 25.3-6. Профессор утверждает, что нет необходимости создавать новую вершину-исток в строкс 1 алгоритма Уоннзон. Профессор считает, что вместо этого можно использовать С' = С, а в роли вершины з использовать любую вершину из множества Ъ' 1С]. Приведите пример взвешенного ориентированного графа С, для которого воплощение идеи профессора в алгоритме 3оннзон даст неправильный ответ.
Затем покажите, что если граф С строго связан (каждая его вершина достижима из любой другой вершины), то результаты работы алгоритма 3оиызон с учетом модификации профессора будут верны. Задачи 25-1. Транзитивиое замыкание динамического графа Предположим, что нужно поддерживать транзитивное замыкание ориентированного графа С = (К Е) по мере добавления ребер в множество Е. Другими словами, после добавления каждого ребра нужно обновить транзитивное замыкание добавленных до этого времени ребер. Предположим, что граф С изначально не содержит ребер, и что транзитивное замыкание должно быть представлено в виде булевой матрицы.
а) Покажите, каким образом после добавления нового ребра в граф С транзитивное замыкание С' = (1; Е*) графа С = (1', Е) можно обновить в течение времени 0 (Уз). б) Приведите пример графа С и ребра е такой, что обновление транзитивного замыкания после добавления ребра е в граф С будет выполняться в течение времени Й (уз) независимо от используемого алгоритма. в) Разработайте эффективный алгоритм обновления транзитивного замыкания по мере добавления ребер в граф. Для любой последова- Часть ЧЬ Алгоритмы для работы с графами 732 тельности и добавлений общее время работы этого алгоритма должно быль равно 2,," 1; = О (Уз), где Ц вЂ” время, необходимое для обновления транзитивного замыкания при добавлении 1-го ребра.
Докажите, что в вашем алгоритме достигается указанная граница времени работы. 25-2. Кратчайшие пути в е-плотном графе Граф С = (У, Е) называется е-плотным (е-депзе), если )Е! = 9 (Уз+') для некоторой константы О < е < 1. Если в алгоритмах, предназначенных для поиска кратчайших путей в е-плотных графах, воспользоваться И-арными неубывающими пирамидами (см. задачу 6-2), то время их выполнения может быть сопоставимо времени выполнения алгоритмов, основанных на применении пирамиды Фибоначчи. При этом удается обойтись без сложных структур данных.
а) Чему равно асимптотическое время работы алгоритмов 1нзвкт, ЕхткАст Мпч и Рвскелзн Кну в зависимости от кратности И и количества элементов Ы-арией неубывающей пирамиды и? Чему равно время работы этих алгоритмов, если выбрать И = 0(п'*), где О < а < 1 — некоторая константа? Сравните время работы этих алгоритмов с амортизированными стоимостями этих операций для пирамиды Фибоначчи. б) Покажите, как в течение времени 0 (Е) вычислить кратчайшие пути из единого истока в е-плотном ориентированном графе С = (У, Е), в котором отсутствуют ребра с отрицательным весом. (Указание: выберите величину И как функцию е.) в) Покажите, как в течение времени О(УЕ) решить задачу поиска кратчайших путей между всеми парами вершин в е-плотиом ориентированном графе С = (У, Е), в котором отсутствуют ребра с отрицательным весом. г) Покажите, как в течение времени 0(УЕ) решить задачу поиска кратчайших путей между всеми парами вершин в е-плотном ориентированном графе С = (У, Е), в котором допускается наличие ребер с отрицательным весом, но отсутствуют циклы с отрицательным весом.
Заключительные замечания Неплохое обсуждение задачи о поиске кратчайших путей между всеми парами вершин содержится в книге Лоулера (Ьачг1ег) [19б], хотя в ней и не анализируются решения для разреженных графов. Алгоритм перемножения матриц он считает Глава 25. Кратчайшие пути между всеми парами вершин 733 результатом народного творчества. Алгоритм Флойда-Варшалла был предложен Флойдом (Е)суд) [89] и основывался на теореме Варшалла (1УагзЬа11) [308], в которой описывается, как найти транзитивное замыкание булевых матриц. Алгоритм Джонсона ()оЬпзоп) взят из статьи [1б8]. Несколько исследователей предложили улучшенные алгоритмы, предназначенные для поиска кратчайших путей с помощью умножения матриц.
Фридман (Ргейпап) [95] показал, что задачу о поиске кратчайшего пути между всеми парами вершин можно решить, выполнив 0 (1'з~з) операций по сравнению суммарных весов ребер; в результате получится алгоритм, время работы которого равно 0 [1 "з (1818 'г'/18]Г)~~~), что несколько лучше соответствующей величины для алгоритма Флойда-Варшалла. Еще одно направление исследований показывает, что к задаче о поиске кратчайших путей между всеми парами вершин можно применить алгоритмы быстрого умножения матриц (см.
заключительные замечания к главе 28). Пусть 0 (и ) — время работы самого производительного алгоритма, предназначенного для перемножения матриц размером и х и; в настоящее время ш < 2.376 [70]. Галил (ОаИ) и Маргалит (Магйарп) [105, 106], а также Зайдель (ЗеЫе1) [270] разработали алгоритмы, решающие задачу о поиске кратчайших путей между всеми парами вершин в неориентированных невзвешенных графах в течение времени 0 (1' р (1')), где р (и) — функция, полилогарифмически ограниченная по п. В плотных графах время работы этих алгоритмов меньше величины О (1' Е), необходимой для Щ поисков в ширину.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
