使用Boost的图形breadth_first_search（）在未加权的无向图中查找路径

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?

我正在使用adjacency_list图,具有无向和未加权的边。我需要找到顶点u和顶点v之间的最短路径。我应该从u开始使用breadth_first_search()吗?到达v时,如何获取路径,如何停止搜索?

thanks!

3 个解决方案

#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.

您应该使用最短路径算法之一,Dijkstra最短路径是最合适的,因为您需要找到两个顶点之间的路径。在boost分配中有一个例子。有几个选项可以从该函数获取输出:通过提供距离属性映射或构建前置映射或编写自定义访问者。

#2

Yes, do breadth_first_search() starting from u.

是的,从你开始做breadth_first_search()。

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

To find the shortest path, start from v:

要找到最短路径,请从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

#3

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

您需要使用最小生成树:搜索算法。这是一个非常简单直接的贪婪算法。

#1

#2