147
правок
Изменения
Нет описания правки
:<tex>d'[u] \gets \min(d'[u], \; d'[v] + \omega(u,v))</tex>
==Корректность алгоритма Форда-Беллмана==
{{Лемма
<br>
}}
==Реализация алгоритма и его корректность==
'''Bellman_Ford(G, s)'''
'''for''' для каждой <tex>v \in V[G]</tex>
<tex> d[v] \leftarrow \mathcal {1} </tex>
<tex>d[s] \leftarrow 0 </tex>
'''for''' <tex> i \leftarrow 1 </tex> '''to''' <tex> \mid V[G] \mid - 1 </tex>
'''for''' для каждого ребра <tex> (u, v) \in E[G] </tex>
'''if''' <tex>d[v] > d[u] + \omega(u, v) </tex>
'''then''' <tex>d[v] \leftarrow d[u] + \omega(u, v)</tex>
'''for''' для каждого ребра <tex> (u, v) \in E[G] </tex>
'''if''' <tex>d[v] > d[u] + \omega(u, v) </tex>
'''then''' '''return''' <tex> \mathit false</tex>
'''return''' <tex> \mathit true </tex>
