Algorithm for selecting different paths

Topics: algorithm
May 8, 2007 at 12:22 AM

Given a source vertex and a destination vertex, there could exist multiple paths which can be traversed unambiguously between them. Which algorithm would provide us these multiple paths?

May 8, 2007 at 8:21 AM
Could you define unambiguously? Are you looking for a particular criteria such as a shortest path?
May 8, 2007 at 4:20 PM
Consider a multi branched graph. There could be a scenario where from the start vertex to target vertex we have 2-3 shortest paths (i.e paths with equal number of vertices b\w start n target).

Which algorithm gives us the list of such paths?

If one provides more vertices in a shortest path, there would be no ambiguity.
May 9, 2007 at 6:30 AM
I don't think QuickGraph has any algorithm for that particular problem.
Dec 17, 2008 at 12:25 PM
I would be interested in the same.

I have a workflow where decisions lead the graph to two or more different paths after the decision node. I not only need to find out if there are indeed branches after a decision node, but also if these branches are joined later on again.

Does anybody have an idea on how to tackle this?
Jan 5, 2009 at 8:52 PM
QuickGraph now provides a way to compute the k-shortest path between 2 nodes.
Apr 5, 2010 at 10:18 PM

Could someone please provide a simple sample of performing this?  I have the latest download, but cannot find that k-Shortest path implementation.


May 11, 2010 at 2:15 PM

Its in QuickGraph.Algorithms.RankedShortestPath.HoffmanPavleyRankedShortestPathAlgorithm<TVertex, TEdge>