Difference between revisions of "Disjoint Path Finding"

From Exterior Memory
Jump to: navigation, search
 
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 22: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.

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:

Bhandari-0.svg

Step 1

Find the (directed) shorest 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 edges which are used in both directions. (here: edge E-D) Bhandari-5.svg

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


Suurballe-0.svg Suurballe-1.svg Suurballe-2a.svg Suurballe-2b.svg Suurballe-3.svg Suurballe-4.svg Suurballe-5.svg