A quick method for finding shortest pairs of disjoint paths

Abstract

Abstract Let G be a directed graph containing n vertices, one of which is a distinguished source s , and m edges, each with a non‐negative cost. We consider the problem of finding, for each possible sink vertex v , a pair of edge‐disjoint paths from s to v of minimum total edge cost. Suurballe has given an O ( n 2 log n )‐time algorithm for this problem. We give an implementation of Suurballe's algorithm that runs in O ( m log( 1+ m/n ) n ) time and O ( m ) space. Our algorithm builds an implicit representation of the n pairs of paths; given this representation, the time necessary to explicitly construct the pair of paths for any given sink is O (1) per edge on the paths.