Boost的Dijkstra的算法教程 [英] Boost's Dijkstra's Algorithm Tutorial

问题描述

我很难弄清楚如何使用Boost的Dijkstra算法.我已经看完了他们的示例和文档，但是我仍然不明白如何使用它们.

I am having difficulty figuring out how to use Boost's Dijkstra's algorithm. I have gone over their example and documentation, but I still cannot understand how to use it.

[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's documentation: http://www.boost.org/doc/libs/1_50_0/libs/graph/doc/dijkstra_shortest_paths.html] [Example of Dijkstra: http://www.boost.org/doc/libs/1_36_0/libs/graph/example/dijkstra-example.cpp]

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

Can someone please offer a step by step explanation with code examples to show how to use Boost's Dijkstra's algorithm? I am using Boost's adjacency_list for my graph, just as in the example link above. (adjacency_list: http://www.boost.org/doc/libs/1_50_0/libs/graph/doc/adjacency_list.html)

推荐答案

关于评论中的问题:

1. 根据示例VC ++的源代码中的注释，使用了命名参数机制.因此，我假设两个分支的想法基本相同，只是VC ++版本更加冗长(我花了很长时间才确定其百分百地确定了它).
2. A property_map将顶点/边映射到与特定顶点/边关联的其他数据.例如.示例中的weightmap将权重(旅行成本)与每个边缘相关联.

3. predecessor_map用于记录所有顶点的路径(对于每个顶点，记录从根开始的路径上的前任).至于为什么需要它:信息是人们经常希望摆脱算法的东西.

1. According to the comment in the sourcecode of the example VC++ has some problems with the named parameter mechanism used. Therefore I'd assume that both branches do basically the same think with the VC++ version just being more verbose (I didn't dive into it long enough to be 100% sure though).
2. A property_map maps vertices/edges to additional data associated with the particular vertex/edge. E.g. the weightmap in the example associates a weight (travelling cost) with each edge.

3. The predecessor_map is used to record the paths for all vertices (for every vertex the predecessor on the path from the root is recorded). As for why it's needed: Well that information is something one often hopes to get out of the algorithm.

说明中清楚列出了参数.请注意两个版本，一个带有命名参数，另一个不带命名参数(后者在VC ++中使用).

The parameters are clearly listed in the description. Note the two versions, one with named parameters and one without (the later being used in VC++).

现在逐步了解中提供的示例代码文档(请注意，我从未真正使用过Boost.Graph，因此这不能保证正确性，而且我只包括相关部分，而省略了VC ++的#if):

now for a somewhat step by step of the example code given in the documentation (note that I never actually used Boost.Graph, so this is no guarantees on correctness, also I only included the relevant parts and omitted the #if for VC++):

  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]));

正如我在评论中亲自提到的那样，我发现柠檬比使用Boost更直观.图，所以也许您可能想看看一下

As I mentioned in the comments personally I find lemon more intuitive to use then Boost.Graph, so maybe you might want to give that a look instead

这篇关于Boost的Dijkstra的算法教程的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！