Content deleted Content added
example |
m sectionize |
||
Line 3:
'''Johnson's algorithm''' is a way to solve the [[all-pairs shortest path problem]] in a [[sparse graph|sparse]], [[weighted graph|weighted]], [[directed graph]] in which some of the edge weights may be [[negative number]]s, but no negative-weight [[cycle (graph theory)|cycles]] exist.
==Algorithm description==
#First, it adds a new [[Vertex (graph theory)|node]] ''q'' to the graph, with a zero weight [[Edge (graph theory)|edge]] connecting ''q'' to each other node.
#Second, it runs the [[Bellman-Ford algorithm]], starting from the new vertex ''q'', to check for negative weight cycles and to find for each vertex ''v'' the least weight ''h''(''v'') of a path from ''q'' to ''v''.
Line 11 ⟶ 12:
In the reweighted graph, all paths between a pair ''s'' and ''t'' of nodes have the same quantity ''h(s)'' -''h(t)'' added to them, so a path that is shortest in the original graph remains shortest in the modified graph and vice versa. However, due to the way the values ''h(v)'' were computed, all modified edge lengths are non-negative, ensuring the optimality of the paths found by Dijkstra's algorithm. The distances in the original graph may be calculated from the distances calculated by Dijkstra's algorithm in the reweighted graph by reversing the reweighting transformation.
==Analysis==
The [[time complexity]] of this algorithm, using [[Fibonacci heap]]s in the implementation of Dijkstra's algorithm, is O(''V''<sup>2</sup>log ''V'' + ''VE''): the algorithm uses O(''VE'') time for the Bellman-Ford stage of the algorithm, and O(''V'' log ''V'' + ''E'') for each of ''V'' instantiations of Dijkstra's algorithm. Thus, when the graph is sparse, the total time can be faster than the [[Floyd-Warshall algorithm]], which solves the same problem in time O(''V''<sup>3</sup>).
| |||