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

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

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

Но если 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] обновляется с u на w; в части а это не приводит к появлению (отрицательного) цикла, а в части b приводит.

Однако при таком отслеживании серии указателей от v можно потратить время до O(n), если дойти по пути до t, так и не обнаружив цикла. Сейчас мы рассмотрим метод, не требующий увеличения время выполнения на O(n).