1

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!

Joel Bodenmann
  • 2,152
  • 2
  • 17
  • 44
kbo
  • 231
  • 1
  • 3
  • 9
  • Maybe this will help to get started: http://stackoverflow.com/questions/14126/how-to-create-a-c-boost-undirected-graph-and-traverse-it-in-depth-first-search – Frank Feb 24 '09 at 16:05

3 Answers3

4

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
Stephen Hsu
  • 5,127
  • 7
  • 31
  • 39
3

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.

hvintus
  • 2,547
  • 21
  • 18
  • 4
    The question is concerned with unweighted graphs. To find shortest path in unweighted graph, the easiest method is breadth-first search. Dijkstra's algorithm solves the single-source shortest-paths problem on a weighted, directed graph. – Stephen Hsu Jun 24 '10 at 09:21
-2

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

Jesse Pepper
  • 3,225
  • 28
  • 48
  • 1
    If I'm not mistaken, a minimum spanning tree will not necessarily contain the shortest path between two specific vertices. – kbo Jan 14 '09 at 13:19
  • I think most minimum spanning tree algorithms are not greedy (in the sense of making greedy, suboptimal choices), but they actually find the optimal minimum spanning tree. – Frank Feb 24 '09 at 16:06
  • @dehmann Not true. There are now two algorithms commonly used, Prim's algorithm and Kruskal's algorithm. Both are greedy algorithms that run in polynomial time. Greedy does not imply a suboptimal choice, it implies taking the best apparent choice without looking at further steps. – Jesse Pepper Feb 26 '09 at 04:26
  • @dehmann... http://en.wikipedia.org/wiki/Dijkstra's_algorithm is also greedy (and optimal). – Jesse Pepper Feb 26 '09 at 04:28
  • @JessePepper Right, but minimum spanning trees are certainly not guaranteed to give you the optimal path between two points. – user1520427 Nov 27 '13 at 10:35
  • @user1520427 it certainly will if it's rooted in the source. – Jesse Pepper Nov 28 '13 at 18:29
  • @JessePepper No, it won't. Consider this really contrived graph with three vertices - A,B,C. Let A be the source and let there be edges (A,B), (A,C), (B,C). Let (A,B) have weight 3, (A,C) weight 2, and (B, C) have weight 2. The minimum spanning tree will have edges (A,C) and (B,C), so the cost from A to B is 4. However, the shortest path cost is 3. – user1520427 Nov 28 '13 at 22:59
  • Ah, quite right. I was writing without thinking, I had just read the djikstra's algorithm Wikipedia article, which falsely states: "It can also be used for finding costs of shortest paths from a single vertex to a single destination vertex by stopping the algorithm once the shortest path to the destination vertex has been determined." Without prior knowledge of the graph, it seems a breadth first search is the only way. – Jesse Pepper Nov 29 '13 at 02:18