# Difference between revisions of "Disjoint Path Finding"

(Created page with " File:Bhandari-0.svg File:Bhandari-1.svg File:Bhandari-2.svg File:Bhandari-3.svg File:Bhandari-4.svg File:Bhandari-5.svg File:Suurballe-0.svg [[Fi...") |
|||

Line 1: | Line 1: | ||

+ | The algorithms to find a shortest path in a graph are well-documented, but the algorithms for finding multiple disjoint (non-overlapping) paths are not so well documented. This is an attempt to explain two of them, Suurballe's algorithm (for finding node-disjoint paths) Bhandari's algorithm (for finding edge-disjoint paths) by means of an example. | ||

+ | |||

+ | I assume that the reader is familiar with algorithms to find a single path, such as: | ||

+ | * Edsgar W. Dijkstra's algorithm (or the A*/Astar algorithm which speeds it up by taking the topological distance to the destination in consideration while sorting the nodes in the queue). | ||

+ | * Bellman-Ford algorithm, which is a variant of Dijkstra's algorithm to allow for edges with negative weight. | ||

+ | |||

+ | ==Bhandari== | ||

+ | |||

+ | Ramesh Bhandari published the following algorithm in his book “Survivable Networks: Algorithms for Diverse Routing” (Kluwer Academic Publishers, 1999). It's a simple variant of Suurballe's algorithm and find 2 or more edge-disjoint paths through a graph. The sum of the costs of all paths is minimum. | ||

+ | |||

+ | ===Example=== | ||

+ | |||

+ | Problem: find the two shortest edge-disjoints paths between A and H in this graph: | ||

[[File:Bhandari-0.svg]] | [[File:Bhandari-0.svg]] | ||

+ | |||

+ | ====Step 1==== | ||

+ | |||

+ | Find the (directed) shorest path p1. (e.g. with Dijkstra's algorithm) | ||

+ | |||

[[File:Bhandari-1.svg]] | [[File:Bhandari-1.svg]] | ||

+ | |||

+ | ====Step 2==== | ||

+ | |||

+ | Make the graph directed (if it wasn't) and replace the edges from the found path with inverse edges with negative costs. | ||

+ | |||

[[File:Bhandari-2.svg]] | [[File:Bhandari-2.svg]] | ||

+ | |||

+ | ====Step 3==== | ||

+ | |||

+ | Find the shortest path p2 in the new graph. Use a modified Dijkstra algorithm such as Bellman-Ford to allow for negative edge weights. | ||

+ | |||

[[File:Bhandari-3.svg]] | [[File:Bhandari-3.svg]] | ||

+ | |||

+ | Repeat steps 2 and 3 as necessary (for ''k''-shortest paths) | ||

+ | |||

+ | ====Step 4==== | ||

+ | |||

+ | Add all shortest paths in the graph. | ||

+ | |||

[[File:Bhandari-4.svg]] | [[File:Bhandari-4.svg]] | ||

+ | |||

+ | ====Step 5==== | ||

+ | |||

+ | Remove all edges which are used in both directions. (here: edge E-D) | ||

[[File:Bhandari-5.svg]] | [[File:Bhandari-5.svg]] | ||

+ | |||

+ | You have now 2 (or k) disjoint shortest paths. | ||

+ | |||

+ | |||

[[File:Suurballe-0.svg]] | [[File:Suurballe-0.svg]] |

## Revision as of 23:25, 30 May 2014

The algorithms to find a shortest path in a graph are well-documented, but the algorithms for finding multiple disjoint (non-overlapping) paths are not so well documented. This is an attempt to explain two of them, Suurballe's algorithm (for finding node-disjoint paths) Bhandari's algorithm (for finding edge-disjoint paths) by means of an example.

I assume that the reader is familiar with algorithms to find a single path, such as:

- Edsgar W. Dijkstra's algorithm (or the A*/Astar algorithm which speeds it up by taking the topological distance to the destination in consideration while sorting the nodes in the queue).
- Bellman-Ford algorithm, which is a variant of Dijkstra's algorithm to allow for edges with negative weight.

## Contents

## Bhandari

Ramesh Bhandari published the following algorithm in his book “Survivable Networks: Algorithms for Diverse Routing” (Kluwer Academic Publishers, 1999). It's a simple variant of Suurballe's algorithm and find 2 or more edge-disjoint paths through a graph. The sum of the costs of all paths is minimum.

### Example

Problem: find the two shortest edge-disjoints paths between A and H in this graph:

#### Step 1

Find the (directed) shorest path p1. (e.g. with Dijkstra's algorithm)

#### Step 2

Make the graph directed (if it wasn't) and replace the edges from the found path with inverse edges with negative costs.

#### Step 3

Find the shortest path p2 in the new graph. Use a modified Dijkstra algorithm such as Bellman-Ford to allow for negative edge weights.

Repeat steps 2 and 3 as necessary (for *k*-shortest paths)

#### Step 4

Add all shortest paths in the graph.

#### Step 5

Remove all edges which are used in both directions. (here: edge E-D)

You have now 2 (or k) disjoint shortest paths.