I am having difficulty figuring out how to use Boost's Dijkstra's algorithm. I have gone over their example and documentation, but I still cannot understand how to use it.
[Boost's documentation: http://www.boost.org/doc/libs/1_50_0/libs/graph/doc/dijkstra_shortest_paths.html] [Example of Dijkstra: http://www.boost.org/doc/libs/1_36_0/libs/graph/example/dijkstra-example.cpp]
Can someone please offer a step by step explanation with code examples to show how to use Boost's Dijkstra's algorithm? I am using Boost's adjacency_list for my graph, just as in the example link above. (adjacency_list: http://www.boost.org/doc/libs/1_50_0/libs/graph/doc/adjacency_list.html)
About the questions in the comments:
property_map
maps vertices/edges to additional data associated with the particular vertex/edge. E.g. the weightmap
in the example associates a weight (travelling cost) with each edge.The predecessor_map
is used to record the paths for all vertices (for every vertex the predecessor on the path from the root is recorded). As for why it's needed: Well that information is something one often hopes to get out of the algorithm.
The parameters are clearly listed in the description. Note the two versions, one with named parameters and one without (the later being used in VC++).
now for a somewhat step by step of the example code given in the documentation (note that I never actually used Boost.Graph, so this is no guarantees on correctness, also I only included the relevant parts and omitted the #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 personally I find lemon more intuitive to use then Boost.Graph, so maybe you might want to give that a look instead