Suurballe's Algorithm

Suurballe's algorithm finds two disjoint paths in a nonnegatively weighted directed graph that connect the same pair of vertices with minimum total length. It was conceived by John W. Suurballe and published in 1974. The algorithm runs Dijkstra's algorithm to find one path, modifies the weights of the graph's edges, and then runs Dijkstra's algorithm a second time, combining the two resulting paths and discarding any edges traversed in opposite directions by both to form the final pair of disjoint paths. The weight modification is similar to the one used in Johnson's algorithm, and the method can be seen as a special case of a minimum cost flow algorithm that repeatedly pushes flow along a shortest augmenting path.