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，所以也許你可能想給那看看，而不是