Johnson's All-Pairs Shortest Paths

Combines Bellman-Ford reweighting with one Dijkstra run per vertex and detects negative cycles.