Source code online books for professionals by professionals

Johnson’s algorithm. Finds shortest paths from every node to all others. Basically runs Dijkstra’s from every node. 
However, it uses a trick so that it also works with negative edge weights: It first runs Bellman–Ford from a new start 
node (with added edges to all existing nodes) and then uses the resulting distances to modify the edge weights of the 
graph. The modified weights are all nonnegative but are set so that the shortest paths in the original graph will also be 
the shortest paths in the modified graph. Running time Q(mn lg n). (See Listing 9-4.)