Lesson plan

Johnson's algorithm

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. It works by using the Bellman–Ford algorithm to compute a transformation of the input graph that removes all negative weights, allowing Dijkstra's algorithm to be used on the transformed graph. It is named after Donald B. Johnson, who first published the technique in 1977. A similar reweighting technique is also used in a version of the successive shortest paths algorithm for the minimum cost flow problem due to Edmonds and Karp, as well as in Suurballe's algorithm for finding two disjoint paths of minimum total length between the same two vertices in a graph with non-negative edge weights.

Back to article

Article summary

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. It works by using the Bellman–Ford algorithm to compute a transformation of the input graph that removes all negative weights, allowing Dijkstra's algorithm to be used on the transformed graph. It is named after Donald B. Johnson, who first published the technique in 1977. A similar reweighting technique is also used in a version of the successive shortest paths algorithm for the minimum cost flow problem due to Edmonds and Karp, as well as in Suurballe's algorithm for finding two disjoint paths of minimum total length between the same two vertices in a graph with non-negative edge weights.

Key claims

  1. publication date: 1977 — source: Wikipedia · confidence 0.95

Discussion questions

  1. Summarise the article in your own words. Which single claim would you verify first, and why?
  2. The record states that the publication date is "1977". What evidence would count against this claim?
  3. Which claim in this article is most likely to be revised as the sources update? How would you check its current status?
  4. If two sources disagreed about one of these facts, what would you need in order to trust one over the other?

Bibliography

  1. Wikipedia https://en.wikipedia.org/w/index.php?oldid=1321323800

Key claims and bibliography are generated from the same tracked claims and sources as the article page.