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

Question

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!

Answer 1

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.

Answer 2

Yes, do breadth_first_search() starting from u.

FOR every vertex i meet
  IF i==v: BREAK
  record predecessor of i as i.p

To find the shortest path, start from v:

PRINT_PATH(u, v)
  IF v==u
    print u
  ELSEIF v.p==NIL
    print 'no path from u to v exists'
  ELSE PRINT_PATH(u, v.p)
    print v

Answer 3

You need to use a minimum spanning tree: search algorithm. It's quite a simple straightforward greedy algorithm.