Johnson's Algorithm

Having compared the relative merits and disadvantages of the Bellman-Ford algorithm and Dijkstra's algorithm, we will now discuss an algorithm that combines both of them to retrieve the shortest paths between every pair of vertices in a graph. Johnson's algorithm provides us with the advantage of being able to utilize the efficiency of Dijkstra's algorithm while still producing correct results for graphs with negative edge weights.

The concept behind Johnson's algorithm is quite novel – to contend with Dijkstra's limitations when dealing with negative weights, Johnson's algorithm simply reweights the edges in the graph so they are uniformly non-negative. This is accomplished with the rather creative use of Bellman-Ford combined with some particularly elegant mathematical logic.

The first step in Johnson's algorithm is to add a new 'dummy' vertex to the graph, which is subsequently connected to every other vertex...