188
правок
Изменения
м
'''Neg_Cycleint[]''' neg_cycle(G, s)''':''' '''for''' для каждой <tex>v \in V</tex> <tex> d[v] \leftarrow = <tex>\mathcal {1} </tex> <tex> p[v] \leftarrow = -1 </tex> <tex> d[s] \leftarrow = 0 </tex> '''for''' <tex> i \leftarrow 1 </tex> = 0 '''to''' <tex>|V| - 1 </tex> '''for''' для каждого ребра <tex> (u, v) \in E </tex> '''if''' <tex>d[v] > d[u] + <tex>\omega(u, v) </tex> '''then''' <tex> d[v] \leftarrow = d[u] + <tex>\omega(u, v)</tex> <tex> p[v] \leftarrow = u</tex> '''for''' для каждого ребра <tex> (u, v) \in E </tex> '''if''' <tex>d[v] > d[u] + <tex>\omega(u, v)</tex> '''then''' '''for''' <tex> i \leftarrow 1 </tex> = 0 '''to''' <tex>|V| - 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>
Нет описания правки
'''for''' k = 0 '''to''' n - 2
'''for''' <tex>v \in V</tex>
'''for''' <tex>(u : vu \; , v) \in E</tex>
d[k + 1][u] = min(d[k + 1][u], d[k][v] + <tex>\omega(u, v)</tex>) <font color="green">// <tex>\omega(u, v)</tex> - вес ребра uv</font>
==Реализация алгоритма и ее корректность==
'''funcbool''' bellman_ford(s)''':'''
'''for''' <tex>v \in V</tex>
d[v] = <tex>\mathcal {1}</tex>
|statement=Пусть <tex>G = (V, E) </tex> {{---}} взвешенный ориентированный граф, <tex> s </tex> {{---}} стартовая вершина. Тогда после завершения <tex> |V| - 1 </tex> итераций цикла для всех вершин, достижимых из <tex>s</tex>, выполняется равенство <tex> d[v] = \delta (s, v) </tex>.
|proof=Рассмотрим произвольную вершину <tex>v</tex>, достижимую из <tex>s</tex>.
Пусть <tex>p = \langle v_0,..., v_{k} \rangle </tex>, где <tex>v_0 = s</tex>, <tex>v_{k} = v</tex> {{---}} кратчайший ациклический путь из <tex> s </tex> в <tex> v </tex>. Путь <tex> p </tex> содержит не более <tex> |V| - 1 </tex> ребер. Поэтому <tex>k \le leqslant |V| - 1</tex>.
Докажем следующее утверждение:
:После <tex>n : (n \le leqslant k)</tex> итераций первого цикла алгоритма, <tex>d[v_n] = \delta(s, v_n) </tex>
Воспользуемся индукцией по <tex>n</tex>:
'''Индукционный переход'''
:Пусть после <tex>n : (n < k)</tex> итераций, верно что <tex>d[v_n] = \delta(s, v_n)</tex>. Так как <tex>(v_n, v_{n + 1})</tex> принадлежит кратчайшему пути от <tex>s</tex> до <tex>v</tex>, то <tex>\delta(s, v_{n+1}) = \delta(s, v_n) + \omega(v_n, v_{n + 1})</tex>. Во время <tex>l + 1</tex> итерации релаксируется ребро <tex>(v_n,v_{n+1})</tex>, следовательно по завершению итерации будет выполнено
::<tex>d[v_{n+1}] \le leqslant d[v_n] + \omega(v_n, v_{n+1}) = \delta(s, v_n) + \omega(v_n, v_{n+1}) = \delta(s, v_{n+1})</tex>.:Ясно, что <tex>d[v_{n+1}] \ge geqslant \delta(s, v_{n+1}) </tex>, поэтому верно что после <tex>l + 1</tex> итерации <tex>d[v_{n+1}] = \delta(s, v_{n + 1})</tex>.
:Индукционный переход доказан.
Из того, что <tex> v_0 = v_{k} </tex> следует, что <tex> \sum\limits^{k}_{i=1} {d[v_{i}]} = \sum \limits_{i=1}^{k} {d[v_{i - 1}]} </tex>.
Получили, что <tex> \sum \limits_{i=1}^{k} {\omega (v_{i-1}, v_{i})} \ge geqslant 0 </tex>, что противоречит отрицательности цикла <tex> c </tex>.
}}
Зная, что вершина <tex> u </tex> лежит на цикле отрицательного веса, можно восстанавливать путь по сохраненным вершинам до тех пор, пока не встретится та же вершина <tex> u </tex>. Это обязательно произойдет, так как в цикле отрицательного веса релаксации происходят по кругу.
== Источники ==
