Изменения

|statement=Пусть <tex>G = (V, E) </tex> -— взвешенный ориентированный граф, <tex> s </tex> — стартовая вершина. Тогда после завершения <tex> \mid V[G] \mid - 1 </tex> итераций цикла для всех вершин, достижимых из <tex>s </tex>, выполняется равенство <tex> d[v] = \delta (s, v) </tex>.|proof=Рассмотрим произвольную вершину <tex> v </tex> , достижимую из <tex> s </tex>, <tex> p = {v_0,..., v_{k}} </tex>, где <tex> v_0 = s </tex>, <tex> v_{k} = v </tex> — кратчайший ациклический путь из <tex> s </tex> в <tex> v </tex>. Путь <tex> p </tex> содержит не более <tex> \mid V[G] \mid - 1 </tex> ребер. На каждой из <tex> \mid V[G] \mid - 1 </tex> итераций цикла релаксируются <tex> \mid E[G] \mid </tex> ребер. Среди ребер, прорелаксированных во время i-й итерации , находится ребро <tex> (v_{i-1}, v_{i}) </tex>. Поэтому выполнены равенства <tex>d[v] = d[v_{k}] = \delta (s, v_{k}) = \delta (s, v))</tex>.

|statement=Пусть <tex>G = (V, E) </tex> -взвешенный ориентированный граф, <tex> s </tex> — стартовая вершина. Если граф <tex> G </tex> не содержит отрицательных циклов, достижимых из вершины <tex> s </tex>, то алгоритм возвращает <tex> true </tex> и для всех <tex> v \in V[G] \ d[v] = \delta (s, v)</tex>. Если граф <tex> G </tex> содержит отрицательные циклы, достижимые из вершины <tex> s </tex>, то алгоритм возвращает <tex> false </tex>|proof=Пусть граф <tex> G </tex> не содержит отрицательных циклов, достижимых из вершины <tex> s </tex>. Тогда если вершина <tex> v </tex> достижима из <tex> s </tex>, то по лемме <tex> d[v] = \delta (s, v)</tex>. Если вершина <tex> v </tex> не достижима из <tex> s </tex>, то <tex> d[v] = \delta (s, v) = \mathcal {1}</tex> из несуществования пути. Теперь докажем , что алгоритм вернет значение <tex> true </tex>. После выполнения алгоритма верно, что для всех <tex> (u, v) \in E[G], \ d[v] = \delta (s, v) \leqslant \delta (s, u) + \omega (u,v) = d[u] + \omega (u,v)</tex>, значит ни одна из проверок не вернет значения <tex> false </tex>.Пусть граф <tex> G </tex> содержит отрицательный цикл <tex> c = {v_0,...,v_{k}} </tex>, где <tex> v_0 = v_{k} </tex>, достижимый из вершины <tex> s </tex>. Тогда <tex>\sum_sum\limits_{i=1}^{k} {\omega (v_{i-1}, v_{i})} < 0 </tex>. Предположим, что алгоритм возвращает <tex> true </tex>, тогда для <tex> i = 1,...,k </tex> выполняется <tex> d[v_{i}] \leqslant d[v_{i-1}] + \omega (v_{i-1}, v_{i}) </tex>. Просуммируем эти неравенства по всему циклу: <tex>\sum_sum\limits_{i=1}^{k} {d[v_{i}]} \leqslant \sum_sum\limits_{i=1}^{k} {d[v_{i-1}]} + \sum_sum\limits_{i=1}^{k} {\omega (v_{i-1}, v_{i})} </tex>. Из того, что <tex> v_0 = v_{k} </tex> следует, что <tex> \sum\limits^{k}_{i=1} {d[v_{i}]} = \sum_sum \limits_{i=1}^{k} {d[v_{i - 1}]} </tex>. Получили, что <tex> \sum_sum \limits_{i=1}^{k} {\omega (v_{i-1}, v_{i})} >= \ge 0 </tex>, что противоречит отрицательности цикла <tex> c </tex>.