'''Johnson's algorithm''' is a way to solve the [[all-pairs shortest path problem]] in a [[sparse matrix|sparse]], [[weighted graph|weighted]], [[directed graph]].
First, it dividesadds a new [[node]] bywith zero weight [[edge]] from it to all other nodes, and runs the [[Bellman-Ford algorithm]] to check for negative weight cycles and find ''h''(''v''), the least weight of a path from the new node to node ''v''. Next it reweights the edges using the nodes' ''h''(''v'') values. Finally for each node, it runs [[Dijkstra's algorithm]] and stores the computed least weight to other nodes, reweighted using the nodes' ''h''(''v'') values, as the final weight. The [[time complexity]] is O(''V''<sup>2</sup>log ''V'' + ''VE'').
