Алгоритмы - построение и анализ (1021735), страница 149
Текст из файла (страница 149)
Сохранение кратчайших путей Как видно из приведенной ниже леммы, легко организовать изменение весов, удовлетворяющее первому из сформулированных выше свойств. Значения весов кратчайших путей, полученные с помощью весовой функции и, обозначены как Б, а веса кратчайших путей, полученных с помощью весовой функции и, — как д. Лемма 25.1 (Изменение весов сохраняет кратчайшие пути). Пусть дан взвешенный ориентированный граф С = (1г, Е) с весовой функцией ю: Š— В., Глава 25. Кратчайшие пути между всеми парами вершин 727 и пусть Ь: Е -> К вЂ” произвольная функция, отображающая вершины на дей- ствительные числа.
Для каждого ребра (и, о) Е Е определим ю(и,о) = ю(и,о)+ Ь(и) — Ь(о). (25.9) Пусть р = (оо, оы..., оь) — произвольный путь из вершины оо в вершину оь. р является кратчайшим путем с весовой функцией ю тогда и только тогда, когда он является кратчайшим путем с весовой функцией ю, т.е. равенство ю(р) = = д (оо, оь) равносильно равенству ю (р) = б (оо, оь).
Кроме того, граф С содержит цикл с отрицательным весом с использованием весовой функции ю тогда и только тогда, когда он содержит цикл с отрицательным весом с использованием весовой функции ю. Доказательство. Начнем с того, что покажем справедливость равенства ю (Р) = ю (р) + Ь (оо) — Ь (оь) Запишем цепочку соотношений (25.10) ь ю (Р) = ~~ ю (о>-» о>) = >=1 ь (ю(о> ыо;)+ Ь(о; 1) — Ь(о;)) >=1 ь = ~~ 'ю (о;-ыо;) + Ь(оо) — Ь(оь) = >=1 = ю (Р) + Ь (оо) — Ь (оь), ю (с) = ю (с) + Ь (оо) — Ь (оь) = ю (с), где предпоследнее равенство легко получается из "телесюпичностн" суммы разностей. Таким образом, вес любого пути р из вершины оо в вершину оь равен ю (р) = = ю (р)+Ь (оо) — Ь (оя).
Если один путь из вершины оо в вершину оь короче другого с использованием весовой функции ю, то он будет короче и с использованием весовой функции ю. Таким образом, равенство ю(р) = Б(оо,оь) выполняется тогда и только тогда, когда ю (р) = Б (оо, оь).
Наюнец, покажем, что граф С содержит цикл с отрицательным весом с использованием весовой функции ю тогда и толью тогда, когда он содержит такой цикл с использованием весовой функции ю. Рассмотрим произвольный цикл с = = (оо, оы..., оь), где оо = оь. В соответствии с уравнением (25.10), выполняется соотношение Часть Ч1. Алгоритмы для работы с графами 728 а следовательно, вес цикла с будет отрицательным с использованием весовой функции ю тогда и только тогда, когда он отрицательный с использованием весовой функции и. Генерация неотрицательных весов путем их изменения Следующая наша цель заключается в том, чтобы обеспечить выполнение второго свойства: нужно, чтобы величина и (и,п) была неотрицательной для всех ребер (и, и) е Е.
Для данного взвешенного ориентированного графа С = (1г, Е) с весовой функцией ю: Š— К мы создадим новый граф С' = (Ъ", Е'), где 1" = У 0 (з) для некоторой новой вершины з ф Ъ' и Е' = Е О ((з, о): с Е Ъ"). Расширим весовую функцию ю таким образом, чтобы для всех вершин ю е У выполнялось равенство тз (з, с) = О. Заметим, что поскольку в вершину з не входит ни одно ребро, эту вершину не содержит ни один кратчайший путь графа С' отличный от того, который исходит из ж Кроме того, граф С' не содержит циклов с отрицательным весом тогда и толью тогда, югда таких циклов не содержит граф С. На рис. 25.6а показан граф С', соответствующий графу С на рис.
25.1. Теперь предположим, что графы С и С' не содержат циклов с отрицательным весом. Определим для всех вершин о е 1г' величину й(п) = б(з, и). Согласно неравенству треугольника (лемма 24.10), для всех ребер (и, и) Е Е' выполняется соотношение Ь(о) < 6(и) + ю (и,о). Таким образом, если мы определим новые веса в в соответствии с уравнением (25.9), то получим и (и, о) = ю (и, с)+6 (и)— — л (с) > О, так что второе свойство удовлетворяется. На рис. 25.6б показан граф С', полученный в результате переопределения весов графа, изображенного на рис.
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 — некоторая константа? Сравните время работы этих алгоритмов с амортизированными стоимостями этих операций для пирамиды Фибоначчи.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
