Boost Dijkstra Algorithm Tutorial

Question

I find it difficult to understand how to use the Boost Dijkstra algorithm. I reviewed their example and documentation, but I still cannot figure out how to use it.

[Acceleration documentation: http://www.boost.org/doc/libs/1_50_0/libs/graph/doc/dijkstra_shortest_paths.html] [Dijkstra example: http://www.boost.org/doc/libs/1_36_0 /libs/graph/example/dijkstra-example.cpp]

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

Answer 1

About questions in the comments:

• According to the comment in the source code of the VC ++ example, there are some problems with the specified parameter mechanism . Therefore, I would suggest that both branches basically also think that the version of VC ++ is simply more complex (I did not dive into it long enough to be 100% sure, though).
• A property_map maps vertices / edges to additional data associated with a particular vertex / edge. For instance. weightmap in the example associates the weight (travel cost) with each edge.

• predecessor_map used to record paths for all vertices (for each vertex, the predecessor is written on the path from the root). As for why this is needed: it’s good that information is something that often hopes to exit the algorithm.

• The parameters are clearly listed in the description . Pay attention to two versions: one with named parameters and one without (later used in VC ++).

now a few step-by-step code of the example provided in the documentation (note that I never used Boost.Graph, so this does not guarantee correctness, I also included only the relevant parts and skipped #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])); 

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