Johnson's algorithm
Computer-based path-finding method / From Wikipedia, the free encyclopedia
Dear Wikiwand AI, let's keep it short by simply answering these key questions:
Can you list the top facts and stats about Johnson%27s algorithm?
Summarize this article for a 10 year old
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.[1][2] It is named after Donald B. Johnson, who first published the technique in 1977.[3]
Class | All-pairs shortest path problem (for weighted graphs) |
---|---|
Data structure | Graph |
Worst-case performance |
A similar reweighting technique is also used 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.[4]