### 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} logn)‐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.

Original language | English (US) |
---|---|

Pages (from-to) | 325-336 |

Number of pages | 12 |

Journal | Networks |

Volume | 14 |

Issue number | 2 |

DOIs | |

State | Published - Jan 1 1984 |

Externally published | Yes |

### All Science Journal Classification (ASJC) codes

- Software
- Information Systems
- Hardware and Architecture
- Computer Networks and Communications

## Fingerprint Dive into the research topics of 'A quick method for finding shortest pairs of disjoint paths'. Together they form a unique fingerprint.

## Cite this

Suurballe, J. W., & Tarjan, R. E. (1984). A quick method for finding shortest pairs of disjoint paths.

*Networks*,*14*(2), 325-336. https://doi.org/10.1002/net.3230140209