4. Обнаружение циклов отрицательного веса

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

В разд. 3.1 отмечалось, что алгоритм Флойда нахождения кратчайших путей между всеми парами вершин может быть использован и для обнаружения в графе циклов отрицательного веса. Кроме того, в тех случаях, когда в графе имеется вершина из которой достижимы все остальные вершины этого графа, для нахождения циклов отрицательного веса можно также использовать алгоритм из разд. 2.2.1 (как это указывается на шаге Если не все вершины графа достижимы из (например, когда является неориентированным графом, составленным не менее чем из двух связных компонент), то алгоритм разд. 2.2.1 завершит работу (как и должно быть) при следующем распределении пометок: у вершин из компоненты, содержащей пометки конечные, а пометки вершин в других компонентах равны В этом случае циклы отрицательного веса, лежащие в других компонентах, не будут обнаружены. Тем не менее во многих важных приложениях алгоритма обнаружения цикла отрицательного веса (см., например, гл. 11, разд. 5) всегда имеется в распоряжении вершина из которой достижимы все остальные вершины. В таких случаях алгоритм из разд. 2.2.1 при поиске циклов отрицательного веса предпочтительней с вычислительной точки зрения, чем алгоритм Флойда.

Правила остановки алгоритма из разд. 2.2.1 даются в форме, позволяющей минимизировать объем вычислений при поиске кратчайших путей из вершины если только в графе отсутствуют циклы отрицательного веса. Эти правила могут быть видоизменены так, чтобы циклы отрицательного веса обнаруживались по возможности быстрее.

После каждого изменения пометки вершины и нахождения подходящей вершины удовлетворяющей соотношению (8.3), можно проверить, действительно ли принадлежит текущему кратчайшему пути от (этот путь можно найти, используя текущие пометки Если это так, то вершина была помечена через и из неравенства следует, что часть текущего кратчайшего пути от вместе с дугой должна образовывать цикл отрицательного веса и работа алгоритма может закончиться. Если же пометка вершины либо не изменяется (в соответствии с (8.3)), либо изменяется, но не будет принадлежать текущему кратчайшему пути от

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