# Difference between revisions of "Disjoint Path Finding"

(→Step 5) |
|||

(6 intermediate revisions by the same user not shown) | |||

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. | + | 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, in particular node-disjoint path finding algorithms. 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: | 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). | * 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. | * Bellman-Ford algorithm, which is a variant of Dijkstra's algorithm to allow for edges with negative weight. | ||

+ | |||

+ | A last remark: I consider myself a 'user' of algorithms, not a developer of algorithms. This means it is likely that the following two algorithms have slight modifications that suited my needs when I originally implemented them and are thus slightly different from their form as originally published. | ||

==Bhandari== | ==Bhandari== | ||

− | Ramesh Bhandari published the following algorithm in his book “Survivable Networks: Algorithms for Diverse Routing” (Kluwer Academic Publishers, 1999). It | + | Ramesh Bhandari published the following algorithm in his book “Survivable Networks: Algorithms for Diverse Routing” (Kluwer Academic Publishers, 1999). It is based on Suurballe's original algorithm, but much simpler to implement. It finds ''k'' (2 or more) edge-disjoint paths through a graph. The sum of the costs of all paths is minimum. |

===Example=== | ===Example=== | ||

Line 17: | Line 19: | ||

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

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

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

Line 50: | Line 52: | ||

==Suurballe== | ==Suurballe== | ||

+ | |||

+ | J.W. Suurballe published his node-disjoint path finding algorithm in 1974. It finds ''k'' (2 or more) node-disjoint paths through a graph. The sum of the costs of all paths is minimum. This is a more strict requirement than Bhandari's algorithm, which does allow two paths to use the same node, as long as they don't use the same edge. | ||

+ | |||

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

+ | |||

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

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

+ | |||

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

+ | |||

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

+ | |||

[[File:Suurballe-1.svg]] | [[File:Suurballe-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:Suurballe-2a.svg]] | [[File:Suurballe-2a.svg]] | ||

+ | |||

+ | Furthermore, duplicate all intermediate vertices part of path p1, into a incoming and outgoing part. The goal is to enforce that as soon as a tree branches onto one of these nodes, the only option is to follow one of the inverse edges created above. Regular edges in the graph either originate at the source node or terminate at the destination node. The inverse edges added above start at the incoming nodes and terminate at the outgoing nodes. | ||

+ | |||

+ | Observe that the start and end node are not split. Obviously, these two nodes are not disjoint (they are included in all paths). | ||

+ | |||

[[File:Suurballe-2b.svg]] | [[File:Suurballe-2b.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:Suurballe-3.svg]] | [[File:Suurballe-3.svg]] | ||

+ | |||

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

+ | |||

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

+ | |||

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

+ | |||

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

+ | |||

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

+ | |||

+ | Remove all inverse edges along with their originals, so they cancel each other out. In this example edge E-D is removed from both paths. | ||

+ | |||

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

+ | |||

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

+ | |||

+ | [[Category:Graph theory]] |

## Latest revision as of 16:07, 25 April 2015

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, in particular node-disjoint path finding algorithms. 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.

A last remark: I consider myself a 'user' of algorithms, not a developer of algorithms. This means it is likely that the following two algorithms have slight modifications that suited my needs when I originally implemented them and are thus slightly different from their form as originally published.

## Contents

## Bhandari

Ramesh Bhandari published the following algorithm in his book “Survivable Networks: Algorithms for Diverse Routing” (Kluwer Academic Publishers, 1999). It is based on Suurballe's original algorithm, but much simpler to implement. It finds *k* (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) shortest 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 inverse edges along with their originals, so they cancel each other out. In this example edge E-D is removed from both paths.

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

## Suurballe

J.W. Suurballe published his node-disjoint path finding algorithm in 1974. It finds *k* (2 or more) node-disjoint paths through a graph. The sum of the costs of all paths is minimum. This is a more strict requirement than Bhandari's algorithm, which does allow two paths to use the same node, as long as they don't use the same edge.

### Example

Problem: find the two shortest node-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.

Furthermore, duplicate all intermediate vertices part of path p1, into a incoming and outgoing part. The goal is to enforce that as soon as a tree branches onto one of these nodes, the only option is to follow one of the inverse edges created above. Regular edges in the graph either originate at the source node or terminate at the destination node. The inverse edges added above start at the incoming nodes and terminate at the outgoing nodes.

Observe that the start and end node are not split. Obviously, these two nodes are not disjoint (they are included in all paths).

#### 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 inverse edges along with their originals, so they cancel each other out. In this example edge E-D is removed from both paths.

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