35
правок
Изменения
→Псевдокод
Строится граф <tex>G' = (V',\;E')</tex>, где <tex>V' = V \cup \{s\}</tex>,
для некоторой новой вершины <tex>s \not\in V</tex>, а <tex>E' = E \cup \{(s,\;v): \omega(s, v) = 0,\ v \in V\}</tex>
'''if''' Bellman_Ford<tex>(G',\;\omega,\;s)</tex> == FALSE
'''then''' out << «Входной граф содержит цикл с отрицательным весом»
'''for''' для каждой вершины <tex>v \in V</tex>
'''do''' <tex>d_{uv} \leftarrow \delta_\varphi(u,\;v) + \varphi(v) - \varphi(u)</tex>
'''return''' Dd
Итого, в начале алгоритм Форда-Беллмана либо строит потенциальную функцию такую, что после перевзвешивания все веса ребер будут неотрицательны, либо выдает сообщение о том, что в графе присутствует отрицательный цикл.
