Disjoint Path Finding

From Exterior Memory
Jump to: navigation, search

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.

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:

Bhandari-0.svg

Step 1

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

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.

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.

Bhandari-3.svg

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

Step 4

Add all shortest paths in the graph.

Bhandari-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.

Bhandari-5.svg

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:

Suurballe-0.svg

Step 1

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

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.

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).

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.

Suurballe-3.svg

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

Step 4

Add all shortest paths in the graph.

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.

Suurballe-5.svg

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