Johnson's algorithm

Here is the dilemma. Dijkstra is fast but cannot handle negative weights; Bellman-Ford handles negatives but is slow. For all-pairs on a large sparse graph with a few negative edges, you would love to run the fast Dijkstra V times — but you cannot, because of those negatives. Johnson's algorithm is the clever workaround: it first re-labels every edge so that all weights become non-negative WITHOUT changing which paths are shortest, and then it is free to run fast Dijkstra from every vertex.

The trick is a potential function. Add a brand-new vertex q connected to every vertex by a zero-weight edge, and run Bellman-Ford once from q to compute h(v), the shortest distance from q to each v (this also detects any negative cycle). Now reweight each edge: w'(u, v) = w(u, v) + h(u) - h(v). Two facts make this work. First, every reweighted edge is non-negative, because h satisfies the triangle inequality h(v) <= h(u) + w(u,v), which rearranges to exactly w'(u,v) >= 0. Second, reweighting changes a whole path's cost only by h(start) - h(end), a term that depends just on the endpoints, so the SAME paths stay shortest — the telescoping h-terms along any path cancel. Then run Dijkstra from every source on the non-negative w', and finally undo the shift: true dist(u, v) = (Dijkstra distance) - h(u) + h(v). Total time is O(V * E log V) with a binary heap, far better than Floyd-Warshall on sparse graphs.

Johnson's is the algorithm of choice for all-pairs shortest paths on large sparse graphs that contain negative edges — it marries Bellman-Ford's tolerance of negatives with Dijkstra's speed. The honest caveats: it is more intricate to implement than Floyd-Warshall, the one-time Bellman-Ford phase is essential (skip it and Dijkstra would simply be wrong on the negatives), and if a negative cycle exists the whole method correctly reports failure, because no consistent potential h can exist.