AlgoVerse

Johnson's algorithm

All-pairs shortest paths with negative edges: Bellman–Ford makes the weights non-negative, then Dijkstra runs from every node.

Dijkstra from every node gives all-pairs shortest paths in O(V · E log V); for sparse graphs that beats Floyd–Warshall (V³). But Dijkstra fails with negative edges. Johnson changes the weights so none is negative while the shortest paths stay the same.

Read the full explanation ↓
Input:
V=5 · E=9 · src=1PDF export

The same graph as Floyd–Warshall, with two negative edges; the potentials come out as h = (0, −1, −5, 0, −4) and the answer matches Floyd–Warshall.

  1. import heapq
  3. INF = float("inf")
  6. def johnson(graph, src):
  7. # 1. Bellman-Ford from a new node q with a 0-edge to every node.
  8. h = {v: 0 for v in graph}
  9. for round_no in range(len(graph)):
  10. changed = False
  11. for u in graph:
  12. for v, w in graph[u]:
  13. if h[u] + w < h[v]:
  14. h[v] = h[u] + w
  15. changed = True
  16. if not changed:
  17. break
  18. for u in graph:
  19. for v, w in graph[u]:
  20. if h[u] + w < h[v]:
  21. return None
  22. # 2. Dijkstra from every node on the reweighted edges.
  23. dist = {}
  24. for s in graph:
  25. d = dijkstra(graph, h, s)
  26. dist[s] = {v: d[v] - h[s] + h[v] for v in graph}
  27. return dist
  30. def dijkstra(graph, h, s):
  31. d = {v: INF for v in graph}
  32. d[s] = 0
  33. heap = [(0, s)]
  34. while heap:
  35. du, u = heapq.heappop(heap)
  36. if du > d[u]:
  37. continue
  38. for v, w in graph[u]:
  39. nd = du + w + h[u] - h[v]
  40. if nd < d[v]:
  41. d[v] = nd
  42. heapq.heappush(heap, (nd, v))
  43. return d

Invariant: After step 1, every edge has h[u] + w ≥ h[v], so the new weight w + h[u] − h[v] is never negative and Dijkstra works.

Start

38-41742-5612345
  • Current node (u)
  • Shortest-path tree so far
  • Edge being checked

Local variables

src'1'

Orange = changed in this step

graph dict
  • '1': [('2', 3), ('3', 8), ('5', -4)]
  • '2': [('4', 1), ('5', 7)]
  • '3': [('2', 4)]
  • '4': [('1', 2), ('3', -5)]
  • '5': [('4', 6)]

Call stack

  1. johnson()line 6
Step 1 of 487
Black = bf_round, row_done · Orange = key stepbf_round: 0/3 · potential: 0/3 · pop: 0/30 · reweight: 0/45 · relax: 0/25 · row_done: 0/5

    How the work grows with input size

    Average of 5 random graphs per n (fixed seeds). Hollow marker = the input on screen.

    • reweight
    • current input (n=5)
    02040604812n = number of nodesreweight
    Show as a table
    nreweight
    48.4
    838
    1254.8
    Explanation

    The idea

    Dijkstra from every node gives all-pairs shortest paths in O(V · E log V); for sparse graphs that beats Floyd–Warshall (V³). But Dijkstra fails with negative edges. Johnson changes the weights so none is negative while the shortest paths stay the same.

    Reweighting

    Give every node a potential h[v] and change each edge's weight to:

    w'(u, v) = w(u, v) + h[u] − h[v]

    The length of every path from s to t changes by the same constant h[s] − h[t], so the order of the paths does not change.

    Where do the potentials come from?

    Add a new node q with a 0-weight edge to everyone and run Bellman–Ford from q: h[v] = δ(q, v). By the triangle inequality h[v] ≤ h[u] + w, so w' ≥ 0. If Bellman–Ford finds a negative cycle, there is no answer.

    What to watch in the trace

    • First the potentials (h in the memory panel) are built; then Dijkstra runs from every node, and the numbers by the nodes are Dijkstra's distances in the new weights.