78
правок
Изменения
Нахождение отрицательного цикла
:Инициализация занимает <tex> \Theta (V) </tex> времени, каждый из <tex> \mid V \mid - 1 </tex> проходов требует <tex> \Theta (E) </tex> времени, обход по всем ребрам для проверки наличия отрицательного цикла занимает <tex>O(E)</tex> времени.<br>Итого алгоритм Беллмана-Форда работает за <tex>O(V E)</tex> времени.
==Нахождение отрицательного цикла==
:Приведенная выше реализация позволяет определить наличие в графе цикла отрицательного веса. Чтобы найти сам цикл, достаточно сохранять массив вершин из которых производится релаксация. Тогда, если после <tex> \mid V \mid - 1 </tex> итерации найдется вершина <tex> u </tex>, расстояние до которой можно уменьшить, то эта вершина либо лежит на каком-нибудь цикле отрицательного веса, либо достижима из него. Чтобы найти вершину, которая лежит на цикле, можно <tex>\mid V \mid - 1</tex> раз пройти назад по предкам из вершины <tex>u</tex>. Так как наибольшая длина пути в графе из <tex>\mid V \mid</tex> вершин равна <tex>\mid V \mid - 1</tex>, то полученная вершина <tex>v</tex> будет гарантированно лежать на отрицательном цикле. Теперь, зная, что вершина <tex>v</tex> лежит на цикле отрицательного веса, можно пройти из нее по предкам, пока не придем в эту же вершину <tex>v</tex>, а это обязательно произойдет, так как в цикле отрицательного веса релаксации происходят по кругу.
'''Neg_Cycle(G, s)'''
'''for''' для каждой <tex>v \in V</tex>
<tex> d[v] \leftarrow \mathcal {1} </tex>
<tex> p[v] \leftarrow -1 </tex>
<tex>d[s] \leftarrow 0 </tex>
'''for''' <tex> i \leftarrow 1 </tex> '''to''' <tex> \mid V \mid - 1 </tex>
'''for''' для каждого ребра <tex> (u, v) \in E </tex>
'''if''' <tex>d[v] > d[u] + \omega(u, v) </tex> '''then'''
<tex>d[v] \leftarrow d[u] + \omega(u, v)</tex>
<tex>p[v] \leftarrow p[u]</tex>
'''for''' для каждого ребра <tex> (u, v) \in E </tex>
'''if''' <tex>d[v] > d[u] + \omega(u, v)</tex> '''then'''
'''for''' <tex> i \leftarrow 1 </tex> '''to''' <tex> \mid V \mid - 1 </tex>
<tex>v \leftarrow p[v]</tex>
<tex>u \leftarrow v</tex>
'''while''' <tex> u \neq p[v]</tex>
<tex>ans.add(v)</tex>
<tex>v \leftarrow p[v]</tex>
<tex>reverse(ans)</tex>
'''break'''
'''return''' <tex> ans </tex>
== Источники ==
:Кормен, Т., Лейзерсон, Ч., Ривест, Р., Штайн, К. Алгоритмы: построение и анализ / пер. с англ. — изд. 2-е — М.: Издательский дом «Вильямс», 2009. — с.672 — 676. — ISBN 978-5-8459-0857-5.
