Tutorial Algoritmo di Dijkstra di Boost

Question

Ho difficoltà a capire come utilizzare l'algoritmo di Dijkstra di Boost. Ho esaminato il loro esempio e la documentazione, ma non riesco ancora a capire come usarlo.

[documentazione del Boost: http://www.boost.org/doc/libs/1_50_0/libs/graph/doc/dijkstra_shortest_paths.html] [Esempio di Dijkstra: http://www.boost.org/ doc/libs/1_36_0/libs/graph/example/dijkstra-example.cpp]

Qualcuno può offrire una spiegazione passo passo con esempi di codice per mostrare come utilizzare l'algoritmo di Dijkstra di Boost? Sto usando l'adjacency_list di Boost per il mio grafico, proprio come nel link di esempio sopra. (Adjacency_list: http://www.boost.org/doc/libs/1_50_0/libs/graph/doc/adjacency_list.html)

Answer 1

Circa le domande nei commenti:

1. accordo con il commento nel codice sorgente dell'esempio VC++ ha alcuni problemi con la named parameter mechanism used. Quindi suppongo che entrambi i rami facciano praticamente lo stesso con la versione VC++, solo per essere più prolissi (non ci siamo tuffati abbastanza a lungo per essere sicuro al 100%).
2. A property_map associa vertici/spigoli a dati aggiuntivi associati al particolare vertice/spigolo. Per esempio. il weightmap nell'esempio associa un peso (costo di viaggio) ad ogni spigolo.

3. Il predecessor_map viene utilizzato per registrare i percorsi per tutti i vertici (per ogni vertice viene registrato il predecessore sul percorso dalla radice). Per quanto riguarda il motivo per cui è necessario: beh quell'informazione è qualcosa che si spera spesso di uscire dall'algoritmo.

4. I parametri sono chiaramente elencati nello description. Notare le due versioni, una con parametri denominati e una senza (la versione successiva viene utilizzata in VC++).

ora un po passo passo dell'esempio codice dato a the documentation (notare che ho mai effettivamente utilizzato Boost.Graph, quindi questo è alcuna garanzia sulla correttezza, anche ho incluso solo le parti rilevanti e omesso il #if per 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])); 

Come ho già detto nei commenti personalmente trovo lemon più intuitivo da usare poi Boost.Graph, così forse si potrebbe desiderare di dare uno sguardo che invece