188
правок
Изменения
Нет описания правки
Используя приведенные формулы, алгоритм можно реализовать методом динамического программирования.
'''for''' <tex>(k = 0 \; .. \; '''to''' n-2)</tex> '''for''' <tex>(v \in V)</tex> '''for''' <tex>(u : vu \; \in E)</tex> <tex>d[k+1][u] \gets \= min(d[k + 1][u], \; d[k][v] + <tex>\omega(uvu, v)</tex>) <font color="green">//<tex>\omega(u, v)</tex> - вес ребра uv</font>
Также релаксацию можно свести к одномерному случаю (одномерный массив будем обозначать <tex>d'</tex>):
==Реализация алгоритма и ее корректность==
'''Bellman_Fordfunc''' bellman_ford(G, s)''':''' '''for''' для каждой <tex>v \in V</tex> <tex> d[v] \leftarrow = <tex>\mathcal {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''' <font color="green">// <tex>\omega(u, v)</tex>- вес ребра uv</font> d[v] \leftarrow = d[u] + <tex>\omega(u, v)</tex> '''for''' для каждого ребра <tex> (u, v) \in E </tex> '''if''' <tex>d[v] > d[u] + <tex>\omega(u, v) </tex> '''thenreturn''' ''false'return' '' <tex> \mathit false</tex> 'return''return''' <tex> \mathit true </tex>''
