Suurballe's algorithm
Encyclopedia
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 Suurballe'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.
Define to be the cost of the shortest path to node from node in the shortest path tree rooted at .
Figure A illustrates a weighted graph G.
Figure B calculates 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 Gt (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 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).
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.
s, both iterations can be performed in time on a graph with vertices and edges. Therefore, the same time bound applies to Suurballe's algorithm.
By using a modified version of Dijkstra's algorithm that simultaneously computes the distances to each vertex in the graphs , it is also possible to find the total lengths of the shortest pairs of paths from a given source vertex to every other vertex in the graph, in an amount of time that is proportional to a single instance of Dijkstra's algorithm.
Theoretical computer science
Theoretical computer science is a division or subset of general computer science and mathematics which focuses on more abstract or mathematical aspects of computing....
and network routing, Suurballe's algorithm is an algorithm for finding two disjoint paths in a nonnegatively-weighted directed graph
Directed graph
A directed graph or digraph is a pair G= of:* a set V, whose elements are called vertices or nodes,...
, so that both paths connect the same pair of vertices
Vertex (graph theory)
In graph theory, a vertex or node is the fundamental unit out of which graphs are formed: an undirected graph consists of a set of vertices and a set of edges , while a directed graph consists of a set of vertices and a set of arcs...
and have minimum total length. The algorithm was conceived by J. W. Suurballe and published in 1974. The main idea of Suurballe's algorithm is to use Dijkstra's algorithm
Dijkstra's algorithm
Dijkstra's algorithm, conceived by Dutch computer scientist Edsger Dijkstra in 1956 and published in 1959, is a graph search algorithm that solves the single-source shortest path problem for a graph with nonnegative edge path costs, producing a shortest path tree...
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
Johnson's algorithm
Johnson's algorithm is a way to find the shortest paths between all pairs of vertices in a sparse directed graph. It allows some of the edge weights to be negative numbers, but no negative-weight cycles may exist...
, 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 be a weighted directed graph containing a set of vertices and a set of directed edges; let be a designated source vertex in , and let be a designated destination vertex.. Let each edge in , from vertex to vertex , have a non-negative cost .Define to be the cost of the shortest path to node from node in the shortest path tree rooted at .
Algorithm
Suurballe's algorithm performs the following steps:- Find the shortest path tree rooted at node by running Dijkstra's algorithm. This tree contains for every vertex , a shortest path from to . Let be the shortest cost path from to . The edges in are called tree edges and the remaining edges are called non tree edges.
- Modify the cost of each edge in the graph by replacing the cost of every edge by . According to the resulting modified cost function, all tree edges have a cost of 0, and non tree edges have a non negative cost.
- Create a residual graph formed from by removing the edges of that are directed into and by reversing the direction of the zero length edges along path .
- Find the shortest path in the residual graph by running Dijkstra's algorithm.
- Discard the reversed edges of from both paths. The remaining edges of and form a subgraph with two outgoing edges at , two incoming edges at , and one incoming and one outgoing edge at each remaining vertex. Therefore, this subgraph consists of two edge-disjoint paths from to and possibly some additional (zero-length) cycles. Return the two disjoint paths from the subgraph.
Example
The following example shows how Suurballe'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 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 Gt (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 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 . 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 heapFibonacci heap
In computer science, a Fibonacci heap is a heap data structure consisting of a collection of trees. It has a better amortized running time than a binomial heap. Fibonacci heaps were developed by Michael L. Fredman and Robert E. Tarjan in 1984 and first published in a scientific journal in 1987...
s, both iterations can be performed in time on a graph with vertices and edges. Therefore, the same time bound applies to Suurballe's algorithm.
Variations
The version of Suurballe's algorithm as described above finds paths that have disjoint edges, but that may share vertices. It is possible to use the same algorithm to find vertex-disjoint paths, by replacing each vertex by a pair of adjacent vertices, one with all of the incoming adjacencies of the original vertex, and one with all of the outgoing adjacencies. Two edge-disjoint paths in this modified graph necessarily correspond to two vertex-disjoint paths in the original graph, and vice versa, so applying Suurballe's algorithm to the modified graph results in the construction of two vertex-disjoint paths in the original graph. Suurballe's original 1974 algorithm was for the vertex-disjoint version of the problem, and was extended in 1984 by Suurballe and Tarjan to the edge-disjoint version.By using a modified version of Dijkstra's algorithm that simultaneously computes the distances to each vertex in the graphs , it is also possible to find the total lengths of the shortest pairs of paths from a given source vertex to every other vertex in the graph, in an amount of time that is proportional to a single instance of Dijkstra's algorithm.