Algorithm
1. Run Dijkstra → tree T with shortest paths. 2. Reweight: w'(u,v) = w(u,v) - d(u) + d(v). 3. Reverse edges on shortest path, negate. 4. Run Dijkstra again. 5. XOR the two paths (edges appearing once) → two edge-disjoint paths.
Advertisement
Why reweighting
Ensures non-negative weights on modified graph, letting us use Dijkstra again instead of Bellman-Ford.
Advertisement
Complexity
Two Dijkstra calls: O((V+E) log V).
Vertex-disjoint variant
Split each vertex v into v_in, v_out with edge of weight 0. Vertex disjoint becomes edge disjoint.