You need all-pairs shortest paths on a graph with 2000 vertices, 20000 edges and some negative edge weights but no negative cycle. Compare running Bellman-Ford from every source against Johnson's algorithm, give both complexities with the numbers substituted, and explain the reweighting that makes Johnson's correct.

You need all-pairs shortest paths on a graph with 2000 vertices, 20000 edges and some negative edge weights but no negative cycle. Compare running Bellman-Ford from every source against Johnson's algorithm, give both complexities with the numbers substituted, and explain the reweighting that makes Johnson's correct.

Approach: Bellman-Ford per source is V times VE. Johnson pays one Bellman-Ford to build a potential, then runs Dijkstra from every source on non-negative weights, and the potential must preserve which path is shortest.

O(V^2 E), about 8 * 10^10 operations, against Johnson's algorithm at O(VE + V^2 log V), about 8 * 10^7, so Johnson's is roughly a thousand times faster here. Johnson's adds a new vertex q with a zero weight edge to every vertex, runs one Bellman-Ford from q to obtain the potential function h(v) = dist(q,v) in O(VE), then applies the reweighting w'(u,v) = w(u,v) + h(u) - h(v). The triangle inequality h(v) <= h(u) + w(u,v) makes w' non-negative, so Dijkstra with a binary heap runs from each source at O(E log V). The reweighting preserves which path is shortest because the correction is telescoping: along any path from u to v the intermediate terms cancel and the new length is the old length plus h(u) - h(v), a constant depending only on the endpoints, so the ranking of paths between a fixed pair is unchanged. Subtract h(u) - h(v) from each computed distance to recover the true one. The initial Bellman-Ford also detects a negative cycle, without which no potential exists.

Follow-up: How does the same potential idea let A* search stay optimal, and what does it require of the heuristic?

Key concepts: johnson's algorithm, potential function, reweighting, telescoping.