Suurballe's algorithm
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 is often used in path routing with default Shared Risk Groups (SRGs).
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. 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 discarding existing edges on path P1 directed towards s and reversing all edges along the path T.
Step 4. Find the shortest path P2 in the residual graph Gu.
Step 5. We find the shortest pair of disjoint paths P1 and P2 by taking the union of the edges in P1 and P2, discarding every edge in one path that whose reversal appears in the other ((u,v) in P1 and (v,u) in P2) and grouping the remaining edges in two paths.
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.