Boost的Dijkstra算法教程

Question

Boost的Dijkstra算法教程

7

我正在研究如何使用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的邻接表作为我的图形，就像上面链接中的示例那样。 (邻接表：http://www.boost.org/doc/libs/1_50_0/libs/graph/doc/adjacency_list.html)

- Qman

1

请提供一些您尝试过但未成功的示例。 - Wug

“..他们的示例和文档”- 你正在使用谁的示例和文档？ - hatchet - done with SOverflow

@hatchet：我猜这是http://www.boost.org/doc/libs/1_38_0/libs/graph/example/dijkstra-example.cpp。 - Robert Harvey

1

你确定你完全理解 Dijkstra 算法了吗？ - Bart

@user1563613：再说一遍，你卡在哪里了？顺便提一下，你也可以使用Lemon，我认为它比Boost.Graph更直观（但这可能只是我的想法）。 - Grizzly

显示剩余4条评论

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Grizzly · Accepted Answer

关于评论中的问题：

根据示例代码中的注释，VC++与所使用的命名参数机制存在一些问题。因此，我认为两个分支基本上都是做相同的事情，只不过 VC++ 版本更冗长（尽管我没有深入研究它，不能百分之百确定）。
property_map 将顶点/边映射到与特定顶点/边相关联的其他数据。例如，在示例中，weightmap 将每个边与其权重（行进成本）相关联。
predecessor_map 用于记录所有顶点的路径（记录从根到每个顶点的前继）。为什么需要这样做：这种信息通常是希望从算法中获取的。
参数在描述中清楚地列出。请注意两个版本，一个带有命名参数，另一个没有（后者在 VC++ 中使用）。

现在来看看文档中给出的示例代码（请注意，我从未真正使用过 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更直观易用，也许你可以考虑使用它。