Difference between revisions of "Disjoint Path Finding"
|Line 43:||Line 43:|
Remove all edges
Remove all edges . edge E-D .
Revision as of 23:27, 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.
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.
Problem: find the two shortest edge-disjoints paths between A and H in this graph:
Find the (directed) shorest path p1. (e.g. with Dijkstra's algorithm)
Make the graph directed (if it wasn't) and replace the edges from the found path with inverse edges with negative costs.
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)
Add all shortest paths in the graph.
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.