Поиск кратчайших путей

Одна из проблем, о которой стоит помнить, — содержит ли версия алгоритма, эф- фективная по затратам памяти, достаточно информации для восстановления самих кратчайших путей? В случае алгоритма выравнивания последовательностей из предыдущего раздела нам пришлось прибегнуть к хитроумному методу «разделяй и властвуй» для восстановления решения в реализации, эффективной по затратам памяти.
Однако на этот раз короткие пути восстанавливаются намного проще.

Чтобы облегчить восстановление кратчайших путей, мы усовершенствуем код: каждый узел v будет сохранять первый узел (после себя) на пути к конечной точ- ке t; обозначим этот первый узелfirst[v]. Значениеfirst[v] обновляется при каждом обновлении расстояния А/[v]. Другими словами, когда значениеМ[v] сбрасывается до минимума ПUП (с w + А∙/[w]), мы присваиваем first[v] узел w, для которого этот

минимум достигается.

Пусть теперь P обозначает направленный «граф указателей», узлами которого являются V, а ребрами — {(v,first[v])}. Ключевой факт заключается в следующем:

(6.27) Если граф указателей P содержит цикл C, то этот цикл должен иметь отрицательную стоимость.

Доказательство. Если first[v] = w в любой момент времени, то должно выпол- няться условие M[v] > cw + M[w]. В самом деле, левая и правая стороны равны после обновления, которое задает first[v] равным w; а поскольку M[ w] может умень- шаться, это уравнение может превратиться в неравенство.

Пусть v1, v2, ..., vk — узлы, входящие в цикл C графа указателей; будем считать, что (v, Vj) — последнее добавляемое ребро. Теперь рассмотрим значения непосред- ственно перед последним обновлением. В этот момент А/[v.] > c⅝⅝| + А/[v.+ J для

всех i = 1,..., к - 1, а такжеA/[v] > c⅛1⅛ + Л/[vJ, потому что мы собираемся обновить M[vk] и изменитьfirst[vk] на v1. При суммировании всех этих неравенств значения

А/[v.] аннулируются, и мы получаем 0 > ^ c⅞i⅛ + tyv отрицательный цикл, как

и утверждалось. ■

Теперь заметим, что если G не содержит отрицательных циклов, то из (6.27) следует, что в графе указателей P никогда не будет циклов.

Для узла v рассмотрим путь, получаемый переходами по ребрам P: от v к first[v] = v1, затем first[v1] = v2, и т. д. Так как граф указателей не содержит циклов, а приемник t — единственный узел, не имеющий исходящего ребра, этот путь должен вести к t. Утверждается, что при завершении алгоритма он действительно будет кратчайшим путем из v в t для графа G.

Доказательство. Рассмотрим узел v; пусть w = first[v]. Так как алгоритм завер- шился, должно выполняться условие M[ v] = cw+M[ w]. Значение M[ t] = 0, а следо- вательно, длина пути, отслеживаемого по графу указателей, равна точно M [v] — что, как мы знаем, является расстоянием кратчайшего пути.

Обратите внимание: в версии алгоритма Беллмана-Форда, более эффективной по затратам памяти, количество ребер в пути, длина которого равна M[v] после i итераций, может существенно превышать i. Например, если граф представляет собой единственный путь из s в t и обновления выполняются в порядке, обратном порядку следования ребер в пути, окончательные значения кратчайшего пути будут получены всего за одну итерацию. Такое происходит не всегда, поэтому говорить об улучшении времени выполнения худшего случая не приходится, но было бы неплохо воспользоваться этим фактом для ускорения алгоритма в тех эк- земплярах, где это все же происходит. Для этого в алгоритме нужно предусмотреть «стоп-сигнал» — некий признак, который сообщит о возможности безопасного завершения перед достижением итерации n - 1.

Таким «стоп-сигналом» является простая последовательность следующих наблюдений: если когда-либо будет выполнена полная итерация i, в которой не изменится ни одно значение M[ v], то ни одно значение M[v] не изменится в буду- щем, потому что будущие итерации будут начинаться с тем же набором элементов массива. Следовательно, выполнение алгоритма может быть безопасно прервано. Обратите внимание: если отдельное значение M[v] остается неизменным, этого недостаточно; для безопасного завершения все эти значения должны остаться не- изменными в течение одной итерации. ■

6.9.

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

Еще по теме Поиск кратчайших путей:

  1. поиск путей утверждения в обществе правозаконности.
  2. Поиск смысла жизни – это поиск бессмертия!
  3. Статья 277. Повреждение путей сообщения и транспортных средств
  4. 2. Договоры об эксплуатации подъездных путей и о подаче и уборке вагонов
  5. МОЧЕВЫВОДЯЩИХ ПУТЕЙ ИНФЕКЦИЯ См. статью УРЕТРИТ. МУРАШКИ ПО ТЕЛУ См. статью ОНЕМЕНИЕ.
  6. Пришло время преодолеть свою зависимость от одного пути и осознать, что есть много путей, ведущих к истине.
  7. ПОИСК ИНФОРМАЦИОННЫЙ
  8. ЧАСТЬ 2 В ПОИСКАХ УТРАЧЕННОГО «Я»
  9. ТЕОРИЯ ПОИСКА СМЫСЛА ЖИЗНЕННОГО
  10. Направление поиска работы
  11. Направление поиска работы
  12. 3.11.6. Поиск на ощупь
  13. Направление поиска работы
  14. Направление поиска работы
  15. Направление поиска работы
  16. Направление поиска работы