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. 2 Credited ToDonald B. Johnson, 1977. 2 Time Complexity
Time Complexity (category)Polynomial Time -- O(n^k) 1 Connections
In Field
Source Wikipedia: Johnson's Algorithm
Sources
1. Johnson's Algorithm (Wikipedia)
Wikipedia infobox: time complexity polynomialQuote, Wikipedia infobox: time complexity polynomial
polynomial
2. 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.
Lead section
It is named after Donald B. Johnson, who first published the technique in 1977.
In Field: Algorithms and Complexity Theory, Lead sentence
Johnson's algorithm is a way to find the shortest paths between all pairs of vertices in an edge-weighted directed graph.
View the Source Wikidata: Johnson's Algorithm
Wikidata Q2345824, class allow-list match (w-wdresolver-0926)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.