# Johnson's Algorithm — All-Pairs Shortest Paths (C++) ## Overview Johnson's algorithm computes all-pairs shortest paths for sparse graphs that may contain negative edges (but not negative cycles). It uses Bellman–Ford once to reweight edges, then runs Dijkstra from each vertex. ## Steps 1. Add a new node connected to every vertex with edge weight 0. 2. Run Bellman–Ford from the new node to compute vertex potentials `h[v]`. 3. Reweight original edges: `w'(u,v) = w(u,v) + h[u] - h[v]` (non-negative). 4. Run Dijkstra from each vertex on reweighted graph, then convert distances back: `dist(u,v) = dist'(u,v) - h[u] + h[v]`. ## Complexity - Bellman–Ford: **O(V·E)** - Dijkstra per vertex: `V * O(E log V)` (with heap) - Good for **sparse** graphs vs Floyd–Warshall on dense graphs. ## Repo `https://github.com/mashrur-rahman-fahim/algorithm/blob/main/johnson.cpp` implements this flow and reweights edges in-place. ## Practical tips - Must check for negative cycles with Bellman–Ford. - Use an efficient priority queue for Dijkstra. ## Source `https://github.com/mashrur-rahman-fahim/algorithm/blob/main/johnson.cpp`.