Johnson's algorithm consists of the following steps:<ref name="clrs"/><ref name="black"/>
#First, a new [[Vertex (graph theory)|node]] {{mathmvar|''q''}} is added to the graph, connected by zero-weight [[Edge (graph theory)|edges]] to each of the other nodes.
#Second, the [[Bellman–Ford algorithm]] is used, starting from the new vertex {{mathmvar|''q''}}, to find for each vertex {{mathmvar|''v''}} the minimum weight {{math|''h''(''v'')}} of a path from {{mathmvar|''q''}} to {{mathmvar|''v''}}. If this step detects a negative cycle, the algorithm is terminated.
#Next the edges of the original graph are reweighted using the values computed by the Bellman–Ford algorithm: an edge from {{mathmvar|''u''}} to {{mathmvar|''v''}}, having length {{mathtmath|''w(u,v)''}}, is given the new length {{math|''w''(''u'',''v)'') + ''h''(''u)'') − ''h''(''v)'')}}.
#Finally, {{mathmvar|''q''}} is removed, and [[Dijkstra's algorithm]] is used to find the shortest paths from each node {{mathmvar|''s''}} to every other vertex in the reweighted graph.
