Johnson's algorithm

<p>Johnson's algorithm is a way to find the <a href="/facts/Shortest_path/g4nsrswr">shortest paths</a> between <a href="/facts/All-pairs_shortest_path_problem/g4nsrswr">all pairs of vertices</a> in an <a href="/facts/Weighted_graph/W0MqKkyE">edge-weighted</a> <a href="/facts/Directed_graph/YBdfQ0um">directed graph</a>. It allows some of the edge weights to be <a href="/facts/Negative_number/LzErzCmI">negative numbers</a>, but no negative-weight <a href="/facts/Cycle_(graph_theory)/Is44edrv">cycles</a> may exist. It works by using the <a href="/facts/Bellman%E2%80%93Ford_algorithm/Sx6INcdr">Bellman–Ford algorithm</a> to compute a transformation of the input graph that removes all negative weights, allowing <a href="/facts/Dijkstra%27s_algorithm/ehun88jl">Dijkstra's algorithm</a> to be used on the transformed graph. It is named after <a href="/facts/Donald_B._Johnson/j0xasuop">Donald B. Johnson</a>, who first published the technique in 1977.
</p><p>A similar reweighting technique is also used in a version of the successive shortest paths algorithm for the <a href="/facts/Minimum_cost_flow/bkYsFJa9">minimum cost flow</a> problem due to Edmonds and Karp, as well as in  <a href="/facts/Suurballe%27s_algorithm/9o4Ss64B">Suurballe's algorithm</a> for finding two disjoint paths of minimum total length between the same two vertices in a graph with non-negative edge weights.
</p>

Johnson's algorithm open-in-new

Johnson's algorithm