Johnson's Algorithm

Donald B. Johnson, 1977

Johnson (1977) handles negative edges by computing potentials h(v) via Bellman-Ford from a virtual source, then reweighting so all edges become non-negative. Dijkstra then runs from each vertex. Total O(V² log V + VE).