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 の adjacency_list を使用しています。(adjacency_list: http://www.boost.org/doc/libs/1_50_0/libs/graph/doc/adjacency_list.html )

4

1 に答える 1

15

コメントの質問について：

  1. サンプル VC++ のソースコードのコメントによると、使用されている名前付きパラメーター メカニズムにいくつかの問題があります。したがって、両方のブランチは基本的に同じように考えており、VC++ バージョンはより冗長になっているだけだと思います (ただし、100% 確信できるほど長く掘り下げることはしませんでした)。
  2. property_map頂点/エッジを、特定の頂点/エッジに関連付けられた追加データにマップします。たとえば、weightmap例の は重み (移動コスト) を各エッジに関連付けます。

  3. はpredecessor_map、すべての頂点のパスを記録するために使用されます (すべての頂点について、ルートからのパスの先行が記録されます)。なぜそれが必要なのかについては: まあ、その情報は、アルゴリズムから得たいと思うことがよくあるものです。

  4. パラメータは説明に明確にリストされています。2 つのバージョンに注意してください。1 つは名前付きパラメーターを使用し、もう 1 つは使用しません (後者は VC++ で使用されます)。

ここで、ドキュメントに記載されているサンプル コードを段階的に説明します(Boost.Graph を実際に使用したことがないことに注意してください。したがって、これは正確性を保証するものではありません。また、関連する部分のみを含め、#ifVC++ の を省略しました)。

  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.Graph より直感的に使用できると思うので、代わりに見てみるとよいかもしれません。

于 2012-08-01T22:53:27.227 に答える