Step 1: Add dummy source
Add super-source connected to all nodes with 0-weight edges. Run Bellman-Ford → h(v) = shortest from super-source.
Advertisement
Step 2: Reweight edges
w'(u,v) = w(u,v) + h(u) - h(v). All non-negative (via triangle inequality). No negative edges anywhere now.
Advertisement
Step 3: Dijkstra from each source
V runs of Dijkstra on reweighted graph. Restore original distances.
Complexity
Bellman-Ford: O(VE). V Dijkstras: O(V × E log V). Total: O(V × E log V).