Suurballe's algorithm

Last updated October 13, 2024

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.^[1] The algorithm was conceived by John W. Suurballe and published in 1974.^[2] 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 output of the algorithm is formed by combining these two paths, discarding edges that are traversed in opposite directions by the paths, and using the remaining edges to form the two paths to return as the output. 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.

The problem of finding two disjoint paths of minimum weight can be seen as a special case of a minimum cost flow problem, where in this case there are two units of "flow" and nodes have unit "capacity". Suurballe's algorithm, also, can be seen as a special case of a minimum cost flow algorithm that repeatedly pushes the maximum possible amount of flow along a shortest augmenting path. The first path found by Suurballe's algorithm is the shortest augmenting path for the initial (zero) flow, and the second path found by Suurballe's algorithm is the shortest augmenting path for the residual graph left after pushing one unit of flow along the first path.

Definitions

Let $G$ be a weighted directed graph with vertex set $V$ and edge set $E$ (figure A); 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 vertex $u$ from vertex $s$ in the shortest path tree rooted at $s$ (figure C).

Note: Node and Vertex are often used interchangeably.

Algorithm

Suurballe's algorithm performs the following steps:

Find the shortest path tree $T$ rooted at node $s$ by running Dijkstra's algorithm (figure C). This tree contains for every vertex $u$ , a shortest path from $s$ to $u$ . Let $P 1$ be the shortest cost path from $s$ to $t$ (figure B). The edges in $T$ are called tree edges and the remaining edges (the edges missing from figure C) are called non-tree edges.
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. For example:
If $u =B, v =E$ , then $w' (u, v) = w (B,E) - d(A,E) + d(A,B) = 2 - 3 + 1 = 0$
If $u =E, v =B$ , then $w' (u, v) = w (E,B) - d(A,B) + d(A,E) = 2 - 1 + 3 = 4$
Create a residual graph $G t$ formed from $G$ by removing the edges of $G$ on path $P 1$ that are directed into $s$ and then reverse the direction of the zero length edges along path $P 1$ (figure D).
Find the shortest path $P 2$ in the residual graph $G t$ by running Dijkstra's algorithm (figure E).
Discard the reversed edges of $P 2$ from both paths. The remaining edges of $P 1$ and $P 2$ 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 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 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 ( $u$ ).

Figure D shows the residual graph G_t with 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(|E|+|V|\log |V|)$ where $|V|$ and $|E|$ are the number of vertices and edges respectively. 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 $u-in$ of the original vertex, and one with all of the outgoing adjacencies $u-out$ . 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.^[3]

By using a modified version of Dijkstra's algorithm that simultaneously computes the distances to each vertex $t$ in the graphs $G t$ , it is also possible to find the total lengths of the shortest pairs of paths from a given source vertex $s$ to every other vertex in the graph, in an amount of time that is proportional to a single instance of Dijkstra's algorithm.

Note: The pair of adjacent vertices resulting from the split are connected by a zero cost uni-directional edge from the incoming to outgoing vertex. The source vertex becomes $s-out$ and the destination vertex becomes $t-in$ .

Related Research Articles

In graph theory, the shortest path problem is the problem of finding a path between two vertices in a graph such that the sum of the weights of its constituent edges is minimized.

<span class="mw-page-title-main">Dijkstra's algorithm</span> Algorithm for finding shortest paths

Dijkstra's algorithm is an algorithm for finding the shortest paths between nodes in a weighted graph, which may represent, for example, road networks. It was conceived by computer scientist Edsger W. Dijkstra in 1956 and published three years later.

<span class="mw-page-title-main">Prim's algorithm</span> Method for finding minimum spanning trees

In computer science, Prim's algorithm is a greedy algorithm that finds a minimum spanning tree for a weighted undirected graph. This means it finds a subset of the edges that forms a tree that includes every vertex, where the total weight of all the edges in the tree is minimized. The algorithm operates by building this tree one vertex at a time, from an arbitrary starting vertex, at each step adding the cheapest possible connection from the tree to another vertex.

The Bellman–Ford algorithm is an algorithm that computes shortest paths from a single source vertex to all of the other vertices in a weighted digraph. It is slower than Dijkstra's algorithm for the same problem, but more versatile, as it is capable of handling graphs in which some of the edge weights are negative numbers. The algorithm was first proposed by Alfonso Shimbel, but is instead named after Richard Bellman and Lester Ford Jr., who published it in 1958 and 1956, respectively. Edward F. Moore also published a variation of the algorithm in 1959, and for this reason it is also sometimes called the Bellman–Ford–Moore algorithm.

In computer science, the Floyd–Warshall algorithm is an algorithm for finding shortest paths in a directed weighted graph with positive or negative edge weights. A single execution of the algorithm will find the lengths of shortest paths between all pairs of vertices. Although it does not return details of the paths themselves, it is possible to reconstruct the paths with simple modifications to the algorithm. Versions of the algorithm can also be used for finding the transitive closure of a relation $, or widest paths between all pairs of vertices in a weighted graph.$

This is a glossary of graph theory. Graph theory is the study of graphs, systems of nodes or vertices connected in pairs by lines or edges.

In optimization theory, maximum flow problems involve finding a feasible flow through a flow network that obtains the maximum possible flow rate.

In graph theory, a path in a graph is a finite or infinite sequence of edges which joins a sequence of vertices which, by most definitions, are all distinct. A directed path in a directed graph is a finite or infinite sequence of edges which joins a sequence of distinct vertices, but with the added restriction that the edges be all directed in the same direction.

In computer science, a topological sort or topological ordering of a directed graph is a linear ordering of its vertices such that for every directed edge (u,v) from vertex u to vertex v, u comes before v in the ordering. For instance, the vertices of the graph may represent tasks to be performed, and the edges may represent constraints that one task must be performed before another; in this application, a topological ordering is just a valid sequence for the tasks. Precisely, a topological sort is a graph traversal in which each node v is visited only after all its dependencies are visited. A topological ordering is possible if and only if the graph has no directed cycles, that is, if it is a directed acyclic graph (DAG). Any DAG has at least one topological ordering, and algorithms are known for constructing a topological ordering of any DAG in linear time. Topological sorting has many applications, especially in ranking problems such as feedback arc set. Topological sorting is possible even when the DAG has disconnected components.

In the mathematical field of graph theory, the distance between two vertices in a graph is the number of edges in a shortest path connecting them. This is also known as the geodesic distance or shortest-path distance. Notice that there may be more than one shortest path between two vertices. If there is no path connecting the two vertices, i.e., if they belong to different connected components, then conventionally the distance is defined as infinite.

Johnson's algorithm is a way to find the shortest paths between all pairs of vertices in an edge-weighted directed graph. It allows some of the edge weights to be negative numbers, but no negative-weight cycles may exist. It works by using the Bellman–Ford algorithm to compute a transformation of the input graph that removes all negative weights, allowing Dijkstra's algorithm to be used on the transformed graph. It is named after Donald B. Johnson, who first published the technique in 1977.

Edge disjoint shortest pair algorithm is an algorithm in computer network routing. The algorithm is used for generating the shortest pair of edge disjoint paths between a given pair of vertices. For an undirected graph G(V, E), it is stated as follows:

Run the shortest path algorithm for the given pair of vertices
Replace each edge of the shortest path by a single arc directed towards the source vertex
Make the length of each of the above arcs negative
Run the shortest path algorithm (Note: the algorithm should accept negative costs)
Erase the overlapping edges of the two paths found, and reverse the direction of the remaining arcs on the first shortest path such that each arc on it is directed towards the destination vertex now. The desired pair of paths results.

In computer science, the Hopcroft–Karp algorithm is an algorithm that takes a bipartite graph as input and produces a maximum-cardinality matching as output — a set of as many edges as possible with the property that no two edges share an endpoint. It runs in $time in the worst case, where is set of edges in the graph, is set of vertices of the graph, and it is assumed that . In the case of dense graphs the time bound becomes, and for sparse random graphs it runs in time with high probability.$

The minimum-cost flow problem (MCFP) is an optimization and decision problem to find the cheapest possible way of sending a certain amount of flow through a flow network. A typical application of this problem involves finding the best delivery route from a factory to a warehouse where the road network has some capacity and cost associated. The minimum cost flow problem is one of the most fundamental among all flow and circulation problems because most other such problems can be cast as a minimum cost flow problem and also that it can be solved efficiently using the network simplex algorithm.

<span class="mw-page-title-main">Shortest-path tree</span>

In mathematics and computer science, a shortest-path tree rooted at a vertex v of a connected, undirected graph G is a spanning tree T of G, such that the path distance from root v to any other vertex u in T is the shortest path distance from v to u in G.

<span class="mw-page-title-main">Pseudoforest</span> Graph with at most one cycle per component

In graph theory, a pseudoforest is an undirected graph in which every connected component has at most one cycle. That is, it is a system of vertices and edges connecting pairs of vertices, such that no two cycles of consecutive edges share any vertex with each other, nor can any two cycles be connected to each other by a path of consecutive edges. A pseudotree is a connected pseudoforest.

In graph theory, the planar separator theorem is a form of isoperimetric inequality for planar graphs, that states that any planar graph can be split into smaller pieces by removing a small number of vertices. Specifically, the removal of ⁠ $⁠$ vertices from an $n$ -vertex graph can partition the graph into disjoint subgraphs each of which has at most ⁠ $⁠$ vertices.

In computer science, the method of contraction hierarchies is a speed-up technique for finding the shortest-path in a graph. The most intuitive applications are car-navigation systems: a user wants to drive from $to using the quickest possible route. The metric optimized here is the travel time. Intersections are represented by vertices, the road sections connecting them by edges. The edge weights represent the time it takes to drive along this segment of the road. A path from to is a sequence of edges ; the shortest path is the one with the minimal sum of edge weights among all possible paths. The shortest path in a graph can be computed using Dijkstra's algorithm but, given that road networks consist of tens of millions of vertices, this is impractical. Contraction hierarchies is a speed-up method optimized to exploit properties of graphs representing road networks. The speed-up is achieved by creating shortcuts in a preprocessing phase which are then used during a shortest-path query to skip over "unimportant" vertices. This is based on the observation that road networks are highly hierarchical. Some intersections, for example highway junctions, are "more important" and higher up in the hierarchy than for example a junction leading into a dead end. Shortcuts can be used to save the precomputed distance between two important junctions such that the algorithm doesn't have to consider the full path between these junctions at query time. Contraction hierarchies do not know about which roads humans consider "important", but they are provided with the graph as input and are able to assign importance to vertices using heuristics.$

<span class="mw-page-title-main">Widest path problem</span> Path-finding using high-weight graph edges

In graph algorithms, the widest path problem is the problem of finding a path between two designated vertices in a weighted graph, maximizing the weight of the minimum-weight edge in the path. The widest path problem is also known as the maximum capacity path problem. It is possible to adapt most shortest path algorithms to compute widest paths, by modifying them to use the bottleneck distance instead of path length. However, in many cases even faster algorithms are possible.

A central problem in algorithmic graph theory is the shortest path problem. One of the generalizations of the shortest path problem is known as the single-source-shortest-paths (SSSP) problem, which consists of finding the shortest paths from a source vertex $to all other vertices in the graph. There are classical sequential algorithms which solve this problem, such as Dijkstra's algorithm. In this article, however, we present two parallel algorithms solving this problem.$

References

↑ Bhandari, Ramesh (1999), "Suurballe's disjoint pair algorithms", Survivable Networks: Algorithms for Diverse Routing, Springer-Verlag, pp. 86–91, ISBN 978-0-7923-8381-9 .
↑ Suurballe, J. W. (1974), "Disjoint paths in a network", Networks, 4 (2): 125–145, doi:10.1002/net.3230040204 .
↑ Suurballe, J. W.; Tarjan, R. E. (1984), "A quick method for finding shortest pairs of disjoint paths" (PDF), Networks, 14 (2): 325–336, doi:10.1002/net.3230140209 .

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[1] Bhandari, Ramesh (1999), "Suurballe's disjoint pair algorithms", Survivable Networks: Algorithms for Diverse Routing, Springer-Verlag, pp. 86–91, ISBN 978-0-7923-8381-9 .

[2] Suurballe, J. W. (1974), "Disjoint paths in a network", Networks, 4 (2): 125–145, doi:10.1002/net.3230040204 .

[3] Suurballe, J. W.; Tarjan, R. E. (1984), "A quick method for finding shortest pairs of disjoint paths" (PDF), Networks, 14 (2): 325–336, doi:10.1002/net.3230140209 .

[1]

[2]

[3]