Boost的Dijkstra算法教程

Question

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

[Boost's documentation：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）

Answer 1

关于注释中的问题：

1. 根据例子VC++的源代码的注释有一些问题与named parameter mechanism used。因此，我认为两个分支的基本原理都与VC++版本基本相同，只是更加冗长（尽管如此，我没有深入到足以肯定100％）。
2. A property_map将顶点/边缘映射到与特定顶点/边缘关联的附加数据。例如。示例中的weightmap将权重（旅行成本）与每个边相关联。

3. predecessor_map用于记录所有顶点（对于记录根路径上的前导者的每个顶点）的路径。至于为什么需要它：那么这些信息是人们经常希望摆脱算法的东西。

4. 参数清楚地列在description中。注意两个版本，一个带有命名参数，另一个没有（后来在VC++中使用）。

现在

了几分一步的the documentation给出的示例代码的步骤（请注意，我从来没有实际使用Boost.Graph，所以这是对正确性没有保证，我也只包括了相关的部分和省略#if为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])); 

正如我在评论中提到我个人认为lemon更直观地再使用Boost.Graph，所以也许你可能想给那看看，而不是