Suurballe's algorithm
Suurballe's algorithm conceived by J.W. Suurballe and published in 1974 [1][2] is an algorithm that solves the problem of finding the shortest pairs of edge-disjoint paths in a network with minimal total edge cost. This algorithm performs a graph transformation of the modified graph which renders non negative values, facilitating the use of Dijkstra's algorithm.
Introduction
Let G(V,E) be a weighted directed graph containing a set of n vertices u Є V, one of which is the source node s and m directed edges (u,v) Є E, each with a non-negative cost w(u,v) from node u to node v. d(s,u) is the cost of path to node u from node s in the shortest path tree rooted at s. A path from node u to node v is shortest if there is no path between u and v of shorter length then d(u,v) will be the length of the shortest path from u to v if a shortest path does exist.
Algorithm
Step 1. Find the shortest path tree, T, rooted at node s by running Dijkstra's algorithm. This tree contains for every vertex u, a shortest path from s to u. Let P1 be the shortest cost path from s to t(destination node). The edges in T are called tree edges and the remaining edges are called non tree edges.
Step 2. Update the cost of each edge by transforming the length of every edge (u,v) by defining w'(u,v) = w(u,v) - d(s,v) + d(s,u). All tree edges have a cost of 0, and non tree edges have a non negative cost.
Step 3. Create a residual graph G u formed from G by removing existing edges on P1 directed towards s and reversing the direction of zero length edges along path P1.
Step 4. Find the shortest path P2 in the residual graph Gu by running Dijkstra's algorithm.
Step 5. Find the shortest pair of disjoint paths by transforming to the original graph G, combine the edges of paths P1 and P2 and discard the interlacing edges between paths P1 and P2.
Analysis and running time
This algorithm requires two iterations of Dijkstra's algorithm. Step 1 of the algorithm has a running time of O(Elog(1+E/V)V) by using Dijkstra's [3] single source shortest path algorithm and O(E) space . Step 2 takes O(E) time, based on the duality principle of linear programming with the following property: For every edge (u,v), w'(u,v) ≥ 0, with equality if (u,v) is a tree edge. For this algorithm is also assumed that every vertex in the weighted direct graph G is reachable from s, then m ≥ n-1 and that n ≥ 2, entailing no loss of generality. It is also assumed that G is antisymmetric which means that if (u,v) is an edge then (v,u) is not an edge.
Example
The following example finds the shortest pair of disjoint paths from the source A to F.
Figure A illustrates a weighted graph G.
Figure B shows the shortest path P1 from A to F (A-B-D-F).
Figure C illustrates the shortest path tree T rooted at A, and the computed distances from A to every vertex.
Figure D shows the updated cost of each edge and the edges of path P1 reversed.
Figure E calculates path P2 in the residual graph Gu (A-C-D-B-E-F).
Figure F illustrates both path P1 and path P2.
Figure G finds the shortest pair of disjoint paths by combining the edges of paths P1 and P2 and then discarding the common edges between both paths P1 and P2 in this case (B-D). As a result we get the two shortest pair of disjoint paths (A-B-E-F) and (A-C-D-F).
References
External links
A quick method for finding shortest pairs of disjoint paths
A note on two problems in connexion with graphs
Bhandari, Ramesh (1999) Survivable networks: algorithms for diverse routing