[Boost-users] graph library: finding single-pair shortest path

From: Matthew Reid (f14_tomcat1_at_[hidden])
Date: 2006-12-27 01:55:52

Hi.

I have a question about using the Dijkstra's shortest paths algorithm of the Boost Graph Library. By default, the algorithm is single-source, finding the shortest path to all nodes from a single source node.

 

Is there a way to use the algorithm so that it finds the single-pair path between a source and destination node? I believe that this will be more efficient than finding single-source paths, since the algorithm can be terminated once the shortest path between the source and destination have been obtained.

 

 I've been thinking about using a visitor to terminate the single-source function once the destination node has been examined, however I am unsure how to handle the termination. I am also unsure as to whether this is the most efficient way of generating a single-pair solution.

 

Can anyone offer any advice on this issue?

Advertisement: Mobiles, computers, handsets, iPODs   and more!