7

Bit of a long shot here as I've not found too much documentation on the HoffmanPavleyRankedShortestPathAlgorithm in QuickGraph, so I'm guessing not a lot of people use it, but I'm having a few issues returning the correct results with the Ranked Shortest Path Algorithm and wonder if anyone had found the same problem.

I'm populating a BiDirectional graph with 1900 Vertices and 20000 Edges, and I've set the graph to return 150 paths. It does this, but it doesn't bring back several paths that would be expected, namely one that should rank in the top 20 shortest paths. My expectation of the system is that if I asked for 150 paths, it would return the 150 shortest paths in order.

Now, when I set it to return over 1000 paths, then the expected path shows up. Has anyone come across a problem like this before and might have a way of refining the graph set up? I can't have the system return 1000 paths because it takes far too long to process.

Here is the relevant code: Graph setup:

BidirectionalGraph<string, TaggedEdge<string, int>> pathGraph = new BidirectionalGraph<string, TaggedEdge<string, int>>();

... add vertices and edges

Algorithm setup:

HoffmanPavleyRankedShortestPathAlgorithm<string, TaggedEdge<string, int>> hoffmanAlgorithm = new HoffmanPavleyRankedShortestPathAlgorithm<string, TaggedEdge<string, int>>(pathGraph, E => 1.0);
try
{
    hoffmanAlgorithm.ShortestPathCount = 150;
    hoffmanAlgorithm.SetRootVertex(startPoint.ToString());
    hoffmanAlgorithm.Compute(startPoint.ToString(), endPoint.ToString());

    foreach (IEnumerable<TaggedEdge<string, int>> path in hoffmanAlgorithm.ComputedShortestPaths)
    {
         //process results...
    }
}

As I said, I'm not overly confident of getting a response here, but thought I'd try anyway. The QuickGraph discussion forum on CodePlex doesn't seem to be manned anymore or I would try there.

Thanks very much

e-on
  • 1,547
  • 8
  • 32
  • 65
  • 1
    I'm not familiar with the algorithm, I'd probably guess it makes trade-offs of accuracy for speed. Maybe try some other ranked shorted path algorithms to compare the accuracy and speed? I found this one trying to research your question: http://code.google.com/p/k-shortest-paths/ Sorry I can't really help – Thymine Nov 28 '12 at 20:15

0 Answers0