81
правка
Изменения
→Псевдокод
'''if''' BellmanFord<tex>(G',\;\omega,\;s)</tex> == ''false''
print "Входной граф содержит цикл с отрицательным весом"
'''return ''' <tex>\varnothing</tex> '''else''' '''for''' <tex>v \in V'</tex> <tex>\varphi(v)</tex> = <tex>\delta(s,\;v)</tex> <font color = green>// <tex>\delta(s,\;v)</tex> вычислено алгоритмом Беллмана — Форда</font> '''for''' <tex>(u,\;v) \in E'</tex> <tex>\omega_\varphi(u,\;v)</tex> = <tex> \omega(u,\;v) + \varphi(u) - \varphi(v)</tex> '''for''' <tex>u \in V</tex> Dijkstra<tex>(G,\;\omega_\varphi,\;u)</tex> '''for''' <tex>v \in V</tex> <tex>d_{uv} \leftarrow \delta_\varphi(u,\;v) + \varphi(v) - \varphi(u)</tex>
'''return''' <tex>d</tex>
Итого, в начале алгоритм Форда — -Беллмана либо строит потенциальную функцию такую, что после перевзвешивания все веса ребер будут неотрицательны, либо выдает сообщение о том, что в графе присутствует отрицательный цикл.
Затем из каждой вершины запускается алгоритм Дейкстры для составления искомой матрицы. Так как все веса ребер теперь неотрицательны, алгоритм Дейкстры будет работать корректно. А поскольку перевзвешивание таково, что кратчайшие пути относительно обеих весовых функций совпадают, алгоритм Джонсона в итоге корректно найдет все кратчайшие пути между всеми парами вершин.
