Johnson's algorithm finds the shortest paths between every pair of vertices in an edge-weighted directed graph, and unlike using Dijkstra's algorithm alone, it allows some edge weights to be negative, so long as the graph contains no negative-weight cycle. It works by first using the Bellman-Ford algorithm to reweight the graph so every edge weight becomes non-negative, then running Dijkstra's algorithm from each vertex on the reweighted graph. Donald B. Johnson published the technique in 1977. This description is adapted from Wikipedia contributors under CC BY-SA 4.0; changes were made. https://creativecommons.org/licenses/by-sa/4.0/
Facts
Time ComplexityO(V^2 log V + V*E) using Fibonacci heaps in the Dijkstra step. 1 Credited ToDonald B. Johnson, 1977. 1 Sources
1. Wikipedia: Johnson's Algorithm
Wikimedia FoundationLead section
Johnson's algorithm is a way to find the shortest paths between all pairs of vertices in an edge-weighted directed graph. It allows some of the edge weights to be negative numbers, but no negative-weight cycles may exist.
Body, complexity discussion
O(|V|^2 log |V| + |V||E|) using Fibonacci heaps in Dijkstra's implementation.
Body, history
Donald B. Johnson first published this technique in 1977.
View the Source Reader Challenges (0)
No disputes yet. Spotted an error or a better source? Open the first one.
Sign in to dispute this or suggest a correction.