205
правок
Изменения
→Псевдокод
=== Псевдокод ===
В алгоритме Джонсона используется [[алгоритм Беллмана — Форда]] и [[алгоритм Дейкстры]]. Алгоритм возврашает обычную матрицу <tex>D = d_{ij}</tex> размером <tex>|V|\times |V|</tex>, где <tex>d_{ij} = \delta(i,j)</tex>, или выдает сообщение о том, что входной граф содержит цикл с отрицательным весом.
Алгоритм Джонсона
Строится граф <tex>G'</tex>
'''if''' Bellman_Ford<tex>(G',\;\omega,\;s)</tex> == FALSE
'''then''' out << «Входной граф содержит цикл с отрицательным весом»
'''else''' '''for''' для каждой <tex>v \in V'</tex>
'''do''' присвоить величине <tex>h(v)</tex> значение <tex>\delta(s,\;v)</tex>,
вычисленное алгоритмом Беллмана — Форда
'''for''' для каждого ребра <tex>(u,\;v) \in E'</tex>
'''do''' <tex>\hat{\omega}(u,\;v) \leftarrow \omega(u,\;v) + h(u) - h(v)</tex>
'''for''' для каждой вершины <tex>u \in V</tex>
'''do''' вычисление с помощью алгоритма Дейкстры
<tex>(G,\;\hat{\omega},\;u)</tex> величин <tex>\hat{\delta}(u,\;v)</tex>
для всех вершин <tex>v \in V</tex>
'''for''' для каждой вершины <tex>v \in V</tex>
'''do''' <tex>d_{uv} \leftarrow \hat{\delta}(u,\;v) + h(v) - h(u)</tex>
'''return''' D
== Сложность ==
