Boost's Dijkstra's Algorithmus Tutorial

Question

Ich habe Schwierigkeiten herauszufinden, wie man Boost's Dijkstra's Algorithmus benutzt. Ich habe ihr Beispiel und ihre Dokumentation durchgelesen, aber ich verstehe immer noch nicht, wie ich sie verwenden soll.

[Boost-Dokumentation: http://www.boost.org/doc/libs/1_50_0/libs/graph/doc/dijkstra_shortest_paths.html] [Beispiel von Dijkstra: http://www.boost.org/ doc/libs/1_36_0/libs/graph/beispiel/dijkstra-beispiel.cpp]

Kann jemand bitte eine Schritt-für-Schritt-Erklärung mit Codebeispielen anbieten, um zu zeigen, wie Boost's Dijkstra's Algorithmus benutzt wird? Ich verwende Boosts Adjazenzliste für mein Diagramm, genau wie im obigen Beispiellink. (Adjacency_list: http://www.boost.org/doc/libs/1_50_0/libs/graph/doc/adjacency_list.html)

Answer 1

über die Fragen in den Kommentaren:

1. Nach dem Kommentar im Quellcode des Beispiels VC++ hat einige Probleme mit den named parameter mechanism used. Daher würde ich annehmen, dass beide Zweige im Grunde die gleichen denken, wobei die VC++ Version nur etwas ausführlicher ist (ich habe mich nicht lange genug damit beschäftigt, um 100% sicher zu sein).
2. Ein property_map mappt Vertices/Edges zu zusätzlichen Daten, die mit dem jeweiligen Vertex/Edge verknüpft sind. Z.B. Die weightmap in dem Beispiel assoziiert ein Gewicht (Reisekosten) mit jeder Kante.

3. Die predecessor_map wird verwendet, um die Pfade für alle Scheitelpunkte aufzuzeichnen (für jeden Scheitelpunkt wird der Vorgänger auf dem Pfad von der Wurzel aufgezeichnet). Warum es benötigt wird: Nun, diese Information hofft man oft, aus dem Algorithmus zu kommen.

4. Die Parameter sind in der description übersichtlich aufgeführt. Beachten Sie die zwei Versionen, eine mit benannten Parametern und eine ohne (letztere wird in VC++ verwendet).

jetzt etwas Schritt für Schritt des in the documentation gegebenen Beispiel-Code (beachten Sie, dass ich nie wirklich Boost.Graph verwendet, so ist dies keine Garantie auf Richtigkeit, auch ich nur die relevanten Teile enthalten und entfallen die #if für 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])); 

Wie ich persönlich in den Kommentaren erwähnt finde ich lemon intuitiver dann Boost.Graph zu verwenden, so vielleicht möchten Sie vielleicht, dass ein Blick stattdessen