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 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.
Suurballe's algorithm performs the following steps: The following example shows how Suurballe's algorithm finds the shortest pair of disjoint paths from A to F.
Figure C illustrates the shortest path tree T rooted at A, and the computed distances from A to every vertex (u).
Figure E calculates path P2 in the residual graph Gt (A–C–D–B–E–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.
The version of Suurballe's algorithm as described above finds paths that have disjoint edges, but that may share vertices.
[3] By using a modified version of Dijkstra's algorithm that simultaneously computes the distances to each vertex t in the graphs Gt, 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.