Edge disjoint shortest pair algorithm

<h2 id="the-modified-dijkstra-algorithm">The Modified Dijkstra Algorithm</h2>
Source:<a class="footnote-ref" id="fnref:7" href="#fn:7">7</a><a class="footnote-ref" id="fnref:8" href="#fn:8">8</a>
G = (V, E)
d(i) – the distance of vertex i (i∈V) from source vertex A; it is the sum of arcs in a possible
path from vertex A to vertex i. Note that d(A)=0;
P(i) – the predecessor of vertex i on the same path.
Z – the destination vertex
Step 1.

Start with d(A) = 0,
d(i) = l (Ai), if i∈ΓA; Γi ≡ set of neighbor vertices of vertex i, l(ij) = length of arc from vertex i to vertex j.
 
 = ∞, otherwise. 
Assign S = V-{A}, where V is the set of vertices in the given graph.
Assign P(i) = A, ∀i∈S.

Step 2.

a) Find j∈S such that d(j) = min d(i), i∈S.
b) Set S = S – {j}.
c) If j = Z (the destination vertex), END; otherwise go to Step 3.

Step 3.

∀i∈Γj, if d(j) + l(ji) < d(i),
a) set d(i) = d(j) + l(ji), P(i) = j.
b) S = S ∪{i}
Go to Step 2.

<h2 id="example">Example</h2>
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 B displays the calculated shortest path  ABCZ from A to Z (in bold lines).
Figure C shows the reversal of the arcs of the shortest path and their negative weights.
Figure D displays the shortest path ADCBZ from A to Z determined in the new transformed. graph of Figure C (this is determined using the modified Dijkstra algorithm (or the BFS algorithm) valid for such negative arcs; there are never any negative cycles in such a transformed graph).
Figure E displays the determined shortest path ADCBZ in the original graph.
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.

<h2 id="discussion">Discussion</h2>
In a nonnegative graph, the modified Dijkstra algorithm functions as the traditional Dijkstra algorithm. In a graph characterized by vertices with degrees of O(d) (d<|V|), the efficiency is O(d|V|), being O(|V|2), in the worst case, as in the traditional Dijkstra's case.
In the transformed graph of the edge disjoint shortest pair algorithm, which contains negative arcs, a given vertex previously "permanently" labeled in Step 2a of the modified Dijkstra algorithm may be revisited and relabeled in Step 3a, and inserted back in vertex set S (Step 3b). The efficiency of the modified Dijkstra in such a transformed graph becomes O(d2|V|), being O(|V|3) in the worst case. Most graphs of practical interest are usually sparse, possessing vertex degrees of O(1), in which case the efficiency of the modified Dijkstra algorithm applied to the transformed graph becomes O(|V|) (or, equivalently, O(|E|)). The edge-disjoint shortest pair algorithm then becomes comparable in efficiency to the <a href="/facts/Suurballe%27s_algorithm/9o4Ss64B">Suurballe's algorithm</a>, which in general is of O(|V|2) due to an extra graph transformation that reweights the graph to avoid negative cost arcs, allowing <a href="/facts/Dijkstra%27s_algorithm/ehun88jl">Dijkstra's algorithm</a> to be used for both shortest path steps. 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. The ensuing simple form further lends itself to easy extensions<a class="footnote-ref" id="fnref:9" href="#fn:9">9</a><a class="footnote-ref" id="fnref:10" href="#fn:10">10</a> to K (>2) disjoint paths algorithms and their variations such as partially disjoint paths when complete disjointness does not exist, and also to graphs with constraints encountered by a practicing networking professional in the more complicated real-life networks.
The vertex disjoint version of the above edge-disjoint shortest pair of paths algorithm is obtained by splitting each vertex (except for the source and destination vertices) of the first shortest path in Step 3 of the algorithm, connecting the split vertex pair by a zero weight arc (directed towards the source vertex), and replacing any incident edge with two oppositely directed arcs, one incident on the vertex of the split pair (closer to the source vertex) and the other arc emanating from the other vertex. The K (>2) versions are similarly obtained, e.g., the vertices of the shortest edge disjoint pair of paths (except for the source and destination vertices) are split, with the vertices in each split pair connected to each other with arcs of zero weight as well as the external edges in a similar manner[8][9]. The algorithms presented for undirected graphs also extend to directed graphs, and apply in general to any problem (in any technical discipline) that can be modeled as a graph of vertices and edges (or arcs).

<h2 id="references">References</h2>

<ol>
<li id="fn:1">Bhandari, Ramesh (1999). Survivable networks: algorithms for diverse routing. Springer. p. 46. ISBN 0-7923-8381-8. <a href="0-7923-8381-8" target="_blank">0-7923-8381-8</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></li>
<li id="fn:2">Ford, L. R. (1956). Network Flow Theory, Report P-923. Santa Monica, California: Rand Corporation. <a href="#fnref:2" class="footnote-back-ref">↩</a></li>
<li id="fn:3">Jones, R. H.; Steele, N. C. (1989). Mathematics in Communication Theory. Chichester: Ellis Harwood (division of John Wiley & Sons). p. 74. ISBN 0-470-21246-2. <a href="0-470-21246-2" target="_blank">0-470-21246-2</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></li>
<li id="fn:4">Bhandari, Ramesh (1999). Survivable Networks: Algorithms for Diverse Routing. Springer. pp. 21–37. ISBN 0-7923-8381-8. <a href="0-7923-8381-8" target="_blank">0-7923-8381-8</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></li>
<li id="fn:5">E. F. Moore (1959) "The Shortest Path through the Maze", Proceedings of the International Symposium on the Theory of Switching, Part II, Harvard University Press, p. 285-292 <a href="#fnref:5" class="footnote-back-ref">↩</a></li>
<li id="fn:6">Kershenbaum, Aaron (1993). Telecommunications Network Design Algorithms. McGraw-Hill. pp. 159–162. ISBN 0-07-034228-8. <a href="0-07-034228-8" target="_blank">0-07-034228-8</a> <a href="#fnref:6" class="footnote-back-ref">↩</a></li>
<li id="fn:7">Bhandari, Ramesh (1999). Survivable Networks: Algorithms for Diverse Routing. Springer. pp. 21–37. ISBN 0-7923-8381-8. <a href="0-7923-8381-8" target="_blank">0-7923-8381-8</a> <a href="#fnref:7" class="footnote-back-ref">↩</a></li>
<li id="fn:8">Bhandari, Ramesh (1994), “Optimal Diverse Routing in Telecommunication Fiber Networks”, Proc. of IEEE INFOCOM, Toronto, Canada, pp. 1498-1508. <a href="#fnref:8" class="footnote-back-ref">↩</a></li>
<li id="fn:9">↑ Bhandari, Ramesh (1997) “Optimal Physically-Disjoint Paths Algorithms and Survivable Networks”,  Proc. of Second IEEE Symposium on Computer and Communications, Alexandria, Egypt, pp. 433-441. <a href="#fnref:9" class="footnote-back-ref">↩</a></li>
<li id="fn:10">Bhandari, Ramesh (1999). Survivable Networks: Algorithms for Diverse Routing. Springer. pp. 175–182, 93–162. ISBN 0-7923-8381-8. <a href="0-7923-8381-8" target="_blank">0-7923-8381-8</a> <a href="#fnref:10" class="footnote-back-ref">↩</a></li>
</ol>

Edge disjoint shortest pair algorithm open-in-new

Edge disjoint shortest pair algorithm