Расширения: улучшенные алгоритмы нахождения кратчайшего пути и отрицательного цикла

В конце раздела 6.8 рассматривалась реализация алгоритма Беллмана-Форда, эф- фективная по затратам памяти, для графов, не содержащих отрицательных циклов.

В этом разделе мы реализуем обнаружение отрицательных циклов способом, не менее эффективным в отношении затрат памяти.

Помимо экономии памяти, он также значительно ускоряет работу алгоритма даже для графов без отрицательных циклов. Реализация будет базироваться на том же графе указателей P, построенном из «первых ребер» (v, first[v]), который использовался в реализации из раздела 6.8. Согласно (6.27) мы знаем, что если граф указателей содержит цикл, то этот цикл имеет отрицательную стоимость, и работа на этом завершается. Но если G содержит отрицательный цикл, гарантирует ли это, что граф указателей будет содержать цикл? Кроме того, сколько лишнего вычислительного времени уйдет на периоди- ческие проверки наличия цикла в P?

В идеале нам хотелось бы определять, появляется ли цикл в графе указателей при каждом добавлении нового ребра (v, w) с first[v] = w. Дополнительное преиму- щество такого «моментального» обнаружения циклов заключается в том, что нам не придется ожидать n итераций, чтобы узнать, содержит ли граф отрицательный цикл: алгоритм может завершиться сразу же после обнаружения отрицательного цикла. Ранее было показано, что если граф G не содержит отрицательных циклов, алгоритм может быть остановлен на ранней стадии, если при какой-то итерации значения кратчайшего пути M [ v] остаются неизменными для всех узлов v. Мо- ментальное обнаружение отрицательного цикла станет аналогичным правилом раннего завершения для графов, содержащих отрицательные циклы.

Рассмотрим новое ребро (v, w) с first[v] = w, добавленное в граф указателей P. Перед добавлением (v, w) граф указателей не содержит циклов, поэтому он со- стоит из путей от каждого узла v к конечной точке t. Наиболее естественный способ проверки того, приведет ли добавление ребра (v, w) к созданию цикла в P, заключается в отслеживании текущего пути от w к t за время, пропорциональное длине этого пути. Если на этом пути будет обнаружен узел v, значит, образовался цикл и, согласно (6.27), граф содержит отрицательный цикл. Пример представлен на рис. 6.26, где указатель first[v] обновляется с и на w; в части а это не приводит к появлению (отрицательного) цикла, а в части b приводит. Однако при таком от- слеживании серии указателей от v можно потратить время до O(n), если дойти по пути до t, так и не обнаружив цикла. Сейчас мы рассмотрим метод, не требующий увеличения время выполнения на O(n).

Мы знаем, что перед добавлением нового ребра (v, w) граф указателей был на- правленным деревом. Другой способ проверки того, приводит ли добавление (v, w) к созданию цикла, основан на рассмотрении всех узлов поддерева, направленного к v. Если w входит в это поддерево, то (v, w) образует цикл; в противном случае этого не происходит. (И снова рассмотрите два примера на рис. 6.26.) Чтобы найти все узлы в поддереве, направленном к v, в каждом узле v необходимо хранить спи- сок всех остальных узлов, ребра которых указывают на v. С такими указателями поддерево можно найти за время, пропорциональное размеру поддерева, указыва- ющего на v, — снова максимум O(n). Однако на этот раз нам удастся извлечь до- полнительную пользу из уже проделанной работы. Обратите внимание на то, что текущее значение расстояния M[х] для всех узлов х в поддереве было вычислено на основании старого значения узла v. Мы только что обновили расстояние узла v, а следовательно, знаем, что расстояния всех этих узлов будут обновлены снова. По-


метим каждый из этих узлов x как «пассивный», удалим ребро (x, first[х]) из графа указателей и не будем использовать x для будущих обновлений, пока не изменится его значение расстояния.

Рис. 6.26. Изменение графа указателей P при обновлении first[v] с и на w. На рис. b это приводит к появлению (отрицательного) цикла, а на рис. a — нет

Такие изменения могут сэкономить немало работы при обновлениях, но как это отразится на времени выполнения в худшем случае? Пометка пассивных узлов по- сле каждого обновления расстояний может потребовать дополнительного времени до O(n). Однако узел может быть помечен как пассивный только в том случае, если в прошлом для него был определен указатель, поэтому затраты времени на пометку пассивных узлов не превышают время, потраченное алгоритмом на обновление расстояний.

А теперь рассмотрим время, проводимое алгоритмом за другими операциями, кроме пометки пассивных узлов. Вспомните, что алгоритм разбит на итерации, а итерация i + 1 обрабатывает узлы, расстояние которых было обновлено на итерации i. Для исходной версии алгоритма в (6.26) мы показали, что после i итераций значение M [v] не превышает значение кратчайшего пути из v в t, ис- пользующего не более i ребер. Однако при большом количестве пассивных узлов на каждой итерации это может быть не так. Например, если кратчайший путь из v в t, использующий максимум i ребер, начинается с ребра e = (v, w) и узел w пас- сивен в этой итерации, обновить значение расстояния M[ v] не удастся, а значит, останется значение, превышающее длину пути через ребро (v, w). Казалось бы, возникает проблема, однако в данном случае путь через ребро (v, w) не является кратчайшим, поэтому у M [ v] позднее будет возможность обновиться еще мень- шим значением.

Итак, вместо простого свойства, действовавшего для M[v] в исходных версиях алгоритма, мы имеем следующее утверждение:

(6.35) Во время работы алгоритма M[v] — длина некоторого простого пути из v в t; путь содержит не менее i ребер, если значение расстояния M[v] обновляется на итерации i; после i итераций значение M[v] представляет длину кратчайшего

пути для всех узлов v, для которых существует кратчайший путь v-t, содержащий не более i ребер.

Доказательство. Указатели first образуют дерево путей к t, из чего следует, что все пути, используемые для обновления расстояний, являются простыми. Тот факт, что обновления на итерации i порождаются путями, содержащими не менее i ребер, легко доказывается индукцией по i. Аналогичным образом индукция используется для доказательства того, что после итерации i значение М[v] представляет рас- стояние для всех узлов v, для которых кратчайший путь из v в t содержит не более i ребер. Обратите внимание: узлы v, для которых М[v] содержит фактическое рас- стояние кратчайшего пути, не могут быть пассивными, так как значение М[ v] будет обновлено при следующей итерации для всех пассивных узлов. ■

Используя это утверждение, мы видим, что время выполнения алгоритма в худшем случае по-прежнему ограничивается O(mn): время, потраченное на по- метку пассивных узлов, игнорируем; каждая итерация реализуется за время O(m), и может быть не более n - 1 итераций, обновляющих значения в массиве М без нахождения отрицательного цикла, так как простые пути могут содержать не более n - 1 ребер. Наконец, время, потраченное на пометку пассивных узлов, ограничи- вается временем, потраченным на обновления. Обсуждение завершается следу- ющим утверждением относительно быстродействия алгоритма в худшем случае: как упоминалось ранее, эта новая версия на практике оказывается самой быстрой реализацией алгоритма для графов, не содержащих отрицательных циклов, и даже ребер с отрицательной стоимостью.

(6.36) Усовершенствованная версия алгоритма, описанная выше, находит от- рицательный цикл в G, если такой цикл существует. Она завершается немедленно, если граф указателей P из указателейfirst[v] содержит цикл C или существует ите- рация, при которой никакие значения расстояний М[v] не изменяются. Алгоритм использует память O(n), выполняется за максимум n итераций и за время O(mn) в худшем случае.

<< | >>
Источник: Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science. 2016

Еще по теме Расширения: улучшенные алгоритмы нахождения кратчайшего пути и отрицательного цикла:

  1. ОБЪЕКТ СЕКСУАЛЬНЫЙ: НАХОЖДЕНИЕ: ПУТЬ
  2. Статья 778. Улучшение нанимателем вещи, переданной в найм
  3. 5.2.12. Укрепление и улучшение места (или мест), придающего уверенность
  4. Тема 6. Модели жизненного цикла
  5. 3. Права и обязанности сторон в связи с улучшением арендованного имущества.
  6. Нахождение Плутона
  7. Глава 6. Модели жизненного цикла
  8. Sшrvig Morten. Базовые алгоритмы Qt 4 (Qt 4's Generic Algorithms), 2000
  9. Нахождение аспектов
  10. АЛГОРИТМ
  11. Нахождение куспидов домов
  12. Психологические аспекты улучшения работы по профилактике дорожно-транспортных нарушений.
  13. ЗОДИАКАЛЬНЫЕ ЗНАКИ И ФАЗЫ ЦИКЛА
  14. 6.2. Примеры моделей жизненного цикла
  15. В.В. Розанов. Из цикла «Эмбрионы»
  16. АЛГОРИТМ УДАЧИ
  17. Упражнение НАХОЖДЕНИЕ АНАЛОГИЧНОГО ПРЕДМЕТА ДОМА
  18. Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science, 2016