compute DijkstraShortestPathAlgorith with a target vertex

Topics: algorithm, graph
Aug 20, 2009 at 7:23 PM
Edited Aug 21, 2009 at 9:39 PM

Hi, keep the good job with this library. Here is my question, is there a way to stop the algorithm after that I reach the wanted vertex in DijkstraShortestPathAlgorithm. In my particular case i use relativelly big graph (42k edge, 15k vertex) and i may have to call it really often. So i  should probably gain time if i could stop it after i reach my target. In my modified version of DijkstraShortestPathAlgorithm i got the target vertex information.

Also i have profile the dijkstra for the same type of graph and ive see that 80% of the compute time is on this line

>>var vertices = this.vertexQueue.ToArray(); from AssertHeap() in DijkstraShortestPathAlgorithm takes 5670 ms and was called 16931 times

since this is just used to do some assert, is there a different way that i could pre validate data to avoid to do it there, or if i delete this validation i may cause trouble to computed graph?

thz in advance

Coordinator
Aug 22, 2009 at 9:12 AM

Please split different questions in different threads. I'll tack the target vertex feature with this thread.

AssertHeap() should not be called on Release build and is for debugging purpose only. Just delete it.

Coordinator
Aug 22, 2009 at 9:12 AM
This discussion has been copied to a work item. Click here to go to the work item and continue the discussion.