CODEWITHSUNDEEP
searchboostshortest-pathboost-graph
kbo
kbo

Reputation: 231

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!

Upvotes: 1

Views: 4437

Answers (3)

Stephen Hsu
Stephen Hsu

Reputation: 5177

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

Upvotes: 4

hvintus
hvintus

Reputation: 2617

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.

Upvotes: 3

Jesse Pepper
Jesse Pepper

Reputation: 3243

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

Upvotes: -2

Related Questions