Edge disjoint shortest pair algorithm

For an undirected graph G(V, E), it is stated as follows: In lieu of the general purpose Ford's shortest path algorithm[2][3] valid for negative arcs present anywhere in a graph (with nonexistent negative cycles), Bhandari[4] provides two different algorithms, either one of which can be used in Step 4.

The main steps of the edge-disjoint shortest pair algorithm are illustrated below:Figure A shows the given undirected graph G(V, E) with edge weights.

Figure C shows the reversal of the arcs of the shortest path and their negative weights.

Figure F displays the determined shortest pair of edge-disjoint paths (ABZ, ADCZ) found after erasing the edge BC common to paths ABCZ and ADCBZ, and grouping the remaining edges suitably.

The reweighting requires building the entire shortest path tree rooted at the source vertex.

By circumventing this additional graph transformation, and using the modified Dijkstra algorithm instead, Bhandari's approach results in a simplified version of the edge disjoint shortest pair algorithm without sacrificing much in efficiency at least for sparse graphs.