Tutorial del algoritmo de Dijkstra de Boost

Question

Tengo dificultades para entender cómo usar el algoritmo de Dijkstra de Boost. He repasado su ejemplo y documentación, pero todavía no puedo entender cómo usarlo.

[Documentación de Boost: http://www.boost.org/doc/libs/1_50_0/libs/graph/doc/dijkstra_shortest_paths.html] [Ejemplo de Dijkstra: http://www.boost.org/ doc/libs/1_36_0/libs/graph/example/dijkstra-example.cpp]

¿Puede alguien ofrecer una explicación paso a paso con ejemplos de código para mostrar cómo usar el algoritmo de Dijkstra de Boost? Estoy usando la lista de adyacencia de Boost para mi gráfico, al igual que en el enlace de ejemplo anterior. (Adjacency_list: http://www.boost.org/doc/libs/1_50_0/libs/graph/doc/adjacency_list.html)

Answer 1

Acerca de las preguntas en los comentarios:

1. De acuerdo con el comentario en el código fuente del ejemplo de VC++ tiene algunos problemas con el named parameter mechanism used. Por lo tanto, supongo que ambas ramas básicamente piensan lo mismo con la versión de VC++ siendo más prolija (no me sumergí en ella el tiempo suficiente para estar 100% seguro).
2. A property_map mapea vértices/bordes a datos adicionales asociados con el vértice/borde particular. P.ej. el weightmap en el ejemplo asocia un peso (costo de viaje) con cada borde.

3. El predecessor_map se utiliza para registrar las rutas para todos los vértices (para cada vértice se registra el predecesor en la ruta desde la raíz). En cuanto a por qué es necesario: Bueno, esa información es algo que a menudo se espera obtener del algoritmo.

4. Los parámetros se enumeran claramente en el description. Tenga en cuenta las dos versiones, una con parámetros nombrados y otra sin (el último se utiliza en VC++).

ahora para un paso a paso un poco del ejemplo de código dado en the documentation (nótese que en realidad nunca utilicé Boost.Graph, así que esto es no hay garantías sobre la exactitud, yo también sólo se incluyeron las partes pertinentes y omite el #if para 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])); 

Como ya he mencionado en los comentarios personalmente me parece lemon más intuitivo de usar que Boost.Graph, así que tal vez es posible que desee dar un vistazo en lugar de que