81
правка
Изменения
Нет описания правки
'''Алгоритм Джонсона''' находит кратчайшие пути между всеми парами вершин (англ. ''All Pairs Shortest PathJohnson's algorithm'') находит кратчайшие пути между всеми парами вершин во взвешенном ориентированном графе с любыми весами ребер, но не имеющем отрицательных циклов.
== Алгоритм ==
Предварительно построим граф <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>
'''function''' Johnson(G): '''int[][]'''
'''if''' Bellman_FordBellmanFord<tex>(G',\;\omega,\;s)</tex> == FALSE '''then'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>
