Изменения
Новая страница: «{{В разработке}} ==Алгоритм== Для заданного взвешенного графа <tex>G = (V, E)</tex> алгоритм находит к…»
{{В разработке}}
==Алгоритм==
Для заданного взвешенного графа <tex>G = (V, E)</tex> алгоритм находит кратчайшие пути из заданной вершины <tex> s </tex> до всех остальных вершин, в случае когда в графе <tex> G </tex> содержатся отрицательные циклы достижимые из <tex> s </tex> алгоритм сообщает, что кратчайших путей не существует.
==Псевдокод==
'''Bellman_Ford(G, s)'''
'''for''' для каждой <tex>v \in V[G]</tex>
'''do''' <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>
'''do''' '''for''' для каждого ребра <tex> (u, v) \in E[G] </tex>
'''do''' '''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>
'''do''' '''if''' <tex>d[v] > d[u] + \omega(u, v) </tex>
'''then''' '''return''' <tex> \mathit false</tex>
'''return''' <tex> \mathit true </tex>
==Алгоритм==
Для заданного взвешенного графа <tex>G = (V, E)</tex> алгоритм находит кратчайшие пути из заданной вершины <tex> s </tex> до всех остальных вершин, в случае когда в графе <tex> G </tex> содержатся отрицательные циклы достижимые из <tex> s </tex> алгоритм сообщает, что кратчайших путей не существует.
==Псевдокод==
'''Bellman_Ford(G, s)'''
'''for''' для каждой <tex>v \in V[G]</tex>
'''do''' <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>
'''do''' '''for''' для каждого ребра <tex> (u, v) \in E[G] </tex>
'''do''' '''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>
'''do''' '''if''' <tex>d[v] > d[u] + \omega(u, v) </tex>
'''then''' '''return''' <tex> \mathit false</tex>
'''return''' <tex> \mathit true </tex>
