Suurballe's algorithm

In theoretical computer science and network routing, Suurballe's algorithm is an algorithm for finding two disjoint paths in a nonnegatively-weighted directed graph, so that both paths connect the same pair of vertices and have minimum total length. The algorithm was conceived by J. W. Suurballe and published in 1974. The main idea of Surballe's algorithm is to use Dijkstra's algorithm to find one path, to modify the weights of the graph edges, and then to run Dijkstra's algorithm a second time. The modification to the weights is similar to the weight modification in Johnson's algorithm, and preserves the non-negativity of the weights while allowing the second instance of Dijkstra's algorithm to find the correct second path.

Definitions

Let G be a weighted directed graph containing a set V of n vertices and a set E of m directed edges; let s be a designated source vertex in G, and let t be a designated destination vertex.. Let each edge (u,v) in E, from vertex u to vertex v, have a non-negative cost w(u,v).

Define d(s,u) to be the cost of the shortest path to node u from node s in the shortest path tree rooted at s.

Algorithm

Surballe's algorithm performs the following steps:

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 P₁ be the shortest cost path from s to t. The edges in T are called tree edges and the remaining edges are called non tree edges.
2. Modify the cost of each edge in the graph by replacing the cost w(u,v) of every edge (u,v) by w'(u,v) = w(u,v) − d(s,v) + d(s,u). According to the resulting modified cost function, all tree edges have a cost of 0, and non tree edges have a non negative cost.
3. Create a residual graph G_t formed from G by removing the edges of G that are directed into s and by reversing the direction of the zero length edges along path P₁.
4. Find the shortest path P₂ in the residual graph G_t by running Dijkstra's algorithm.
5. Discard the reversed edges of P₂ from both paths. The remaining edges of P₁ and P₂ form a subgraph with two outgoing edges at s, two incoming edges at t, and one incoming and one outgoing edge at each remaining vertex. Therefore, this subgraph consists of two edge-disjoint paths from s to t and possibly some additional (zero-length) cycles. Return the two disjoint paths from the subgraph.

Example

The following example shows how Surballe's algorithm finds the shortest pair of disjoint paths from A to F.

Figure A illustrates a weighted graph G.

Figure B calculates the shortest path P₁ 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 'P₁ reversed.

Figure E calculates path P₂ in the residual graph G_t (A–C–D–B–E–F).

Figure F illustrates both path P₁ and path P₂.

Figure G finds the shortest pair of disjoint paths by combining the edges of paths P₁ and P₂ and then discarding the common reversed edges between both paths (B–D). As a result we get the two shortest pair of disjoint paths (A–B–E–F) and (A–C–D–F).

Correctness

The weight of any path from s to t in the modified system of weights equals the weight in the original graph, minus d(s,t). Therefore, the shortest two disjoint paths under the modified weights are the same paths as the shortest two paths in the original graph, although they have different weights.

Suurballe's algorithm may be seen as a special case of the successive shortest paths method for finding a minimum cost flow with total flow amount two from s to t. The modification to the weights does not affect the sequence of paths found by this method, only their weights. Therefore the correctness of the algorithm follows from the correctness of the successive shortest paths method.

Analysis and running time

This algorithm requires two iterations of Dijkstra's algorithm. Using Fibonacci heaps, both iterations can be performed in time O(m + n log n). Therefore, the same time bound applies to Surballe's algorithm.

See also

• Edge disjoint shortest pair algorithm