Content deleted Content added
Luckas-bot (talk | contribs) m r2.7.1) (robot Adding: uk:Алгоритм Джонсона |
→Algorithm description: - Helps with clarity |
||
Line 8:
==Algorithm description==
Johnson's algorithm consists of the following steps:
#First, a new [[Vertex (graph theory)|node]] {{math|''q''}} is added to the graph, connected by zero-weight [[Edge (graph theory)|edges]] to each of the other
#Second, the [[Bellman–Ford algorithm]] is used, starting from the new vertex {{math|''q''}}, to find for each vertex {{math|''v''}} the least weight {{math|''h''(''v'')}} of a path from {{math|''q''}} to {{math|''v''}}. If this step detects a negative cycle, the algorithm is terminated.
#Next the edges of the original graph are reweighted using the values computed by the Bellman–Ford algorithm: an edge from {{math|''u''}} to {{math|''v''}}, having length {{math|''w(u,v)''}}, is given the new length {{math|''w(u,v)'' + ''h(u)'' − ''h(v)''}}.
| |||