c++ - Boost的Dijkstra算法教程

Question

我很难弄清楚如何使用 Boost 的 Dijkstra 算法。我已经查看了他们的示例和文档，但我仍然无法理解如何使用它。

[Boost 的文档:http://www.boost.org/doc/libs/1_50_0/libs/graph/doc/dijkstra_shortest_paths.html][Dijkstra 的例子:http://www.boost.org/doc/libs/1_36_0/libs/graph/example/dijkstra-example.cpp]

有人可以提供带有代码示例的分步说明来说明如何使用 Boost 的 Dijkstra 算法吗？我正在为我的图表使用 Boost 的 adjacency_list，就像上面的示例链接一样。 (邻接列表:http://www.boost.org/doc/libs/1_50_0/libs/graph/doc/adjacency_list.html)

Answer 1

关于评论中的问题:

1. 根据示例源代码中的注释，VC++ 对 named parameter mechanism used 有一些问题。 .因此，我假设这两个分支的想法基本相同，只是 VC++ 版本更冗长(尽管我没有深入研究它足够长的时间以确保 100% 确定)。
2. property_map 将顶点/边映射到与特定顶点/边关联的附加数据。例如。示例中的 weightmap 将权重(移动成本)与每条边相关联。

3. predecessor_map 用于记录所有顶点的路径(对于每个顶点，记录从根开始的路径上的前驱)。至于为什么需要它:好吧，这些信息是人们经常希望从算法中得到的东西。

4. description中清楚地列出了参数.注意这两个版本，一个有命名参数，一个没有(后者在 VC++ 中使用)。

现在逐步了解 the documentation 中给出的示例代码(请注意，我从未真正使用过 Boost.Graph，所以这不能保证正确性，而且我只包含了相关部分并省略了 VC++ 的 #if):

  const int num_nodes = 5;
  //names of graph nodes
  enum nodes { A, B, C, D, E };
  char name[] = "ABCDE";
  //edges of the graph
  Edge edge_array[] = { Edge(A, C), Edge(B, B), Edge(B, D), Edge(B, E),
    Edge(C, B), Edge(C, D), Edge(D, E), Edge(E, A), Edge(E, B)
  };
  //weights/travelling costs for the edges
  int weights[] = { 1, 2, 1, 2, 7, 3, 1, 1, 1 };
  int num_arcs = sizeof(edge_array) / sizeof(Edge);

  //graph created from the list of edges
  graph_t g(edge_array, edge_array + num_arcs, weights, num_nodes);
  //create the property_map from edges to weights
  property_map<graph_t, edge_weight_t>::type weightmap = get(edge_weight, g);

  //create vectors to store the predecessors (p) and the distances from the root (d)
  std::vector<vertex_descriptor> p(num_vertices(g));
  std::vector<int> d(num_vertices(g));
  //create a descriptor for the source node
  vertex_descriptor s = vertex(A, g);

  //evaluate dijkstra on graph g with source s, predecessor_map p and distance_map d
  //note that predecessor_map(..).distance_map(..) is a bgl_named_params<P, T, R>, so a named parameter
  dijkstra_shortest_paths(g, s, predecessor_map(&p[0]).distance_map(&d[0]));

正如我个人在评论中提到的，我发现 lemon使用起来比 Boost.Graph 更直观，所以也许您可能想看看它