Johnson's Algorithm
An interactive, step-by-step visualisation of Johnson's Algorithm.
- Category
- Graphs
- Time complexity
- O(V·E log V)
- Space complexity
- O(V²)
Pseudocode
add virtual source with 0-weight edges to all nodes Bellman-Ford from it → potentials h(v) reweight: w'(u,v) = w(u,v)+h(u)-h(v) ≥ 0 Dijkstra from every node on reweighted graph un-reweight distances back
Reference implementation
h = bellman_ford(graph_with_virtual_source)
for u, v, w in edges: reweighted[u][v] = w + h[u] - h[v]
for s in nodes:
d = dijkstra(reweighted, s)
for v in nodes: dist[s][v] = d[v] - h[s] + h[v]