Finding only the shortest path

Topics: algorithm, graph
Apr 28, 2010 at 9:23 PM

Hello, i want to ask if there is any way to generate the shortest path from node A to node B

without generating the shortest paths to all the other nodes (stop when node B is in the examined set)

with A-star.

 

I want to plug QuickGraph into a game and thus generating all the paths is not allowed from the time

limitations the environment imposes.

 

Thanks in advance,

Xtapodi Kataifi.

May 11, 2010 at 2:26 PM

IMHO you should add delegate to algorithm DiscoverVertex event with following manner:

astar.DiscoverVertex(TVertex v) += delegate (TVertex v){
if (v == vertexB) astar.Services.CancelManager.Cancel();
}
astar.Compute(vertexA);

It should stop the algorithm after current iteration.

Cheers, Witek