searchboostshortest-pathboost-graph

Using Boost's graph breadth_first_search() to find a path in an unweighted, undirected graph

I'm using an adjacency_list graph, with undirected and unweighted edges. I need to find a shortest path between vertex u and vertex v. Should I use breadth_first_search() starting from u? When reaching v, how do I obtain the path, and how do I stop the search?

thanks!

Solution

  • You should use one of the shortest path algorithms, Dijkstra Shortest Path being the most suitable since you need to find the path between just two vertexes. There is an example for its usage in the boost distribution. There are several options for obtaining output from that function: either by supplying a distance property map or build a predecessor map or writing a custom visitor.