Boost Graph Library: Shortest path problem
Hi, I have a problem with using (actually with finding the correct function for my problem) the BGL. What I have is 5000 cities (vertices), 14000 roads (edges) between them (directional roads)... And what I want to know is which roads I have to take to encounter the least cities on my way. Every edge has a weight of 1... So the documentation points me to using the breadth_first_search algorithm. But this function - as far as I can see - goes through the entire graph. I don't see any way to stop it (for example when it has discovered my targetcity)?? Is it possible someone can point me where I can have a look at? In short I need to calculate (a lot) of roads from different cities to other cities (so it's not that I always have the same root vertex). Thanks for any suggestion! Steven Van Ingelgem
On 4/7/06, Steven Van Ingelgem
What I have is 5000 cities (vertices), 14000 roads (edges) between them (directional roads)... And what I want to know is which roads I have to take to encounter the least cities on my way.
Every edge has a weight of 1... So the documentation points me to using the breadth_first_search algorithm.
But this function - as far as I can see - goes through the entire graph. I don't see any way to stop it (for example when it has discovered my targetcity)??
Is it possible someone can point me where I can have a look at?
Yes, just throw an exception with a bfs visitor when it has discovered your target city. Look at in archive of this mailing list, their are some examples how to do that. Regards, -- Johan
participants (2)
-
Johan Oudinet -
Steven Van Ingelgem