Boost's Dijkstra's Algorithm Tutorial

Question

Mam trudności z ustaleniem sposobu użycia algorytmu Dostrist Boost. Przeszedłem przez ich przykład i dokumentację, ale nadal nie mogę zrozumieć, jak z niego korzystać.

[dokumentacji Boost to: http://www.boost.org/doc/libs/1_50_0/libs/graph/doc/dijkstra_shortest_paths.html] [Przykład Dijkstra: http://www.boost.org/ doc/libs/1_36_0/libs/graph/example/dijkstra-example.cpp]

Czy ktoś może zaoferować wyjaśnienie krok po kroku za pomocą przykładów kodu, aby pokazać, jak wykorzystać algorytm Dostrista Boosta? Używam listy adjacency_ Boost dla mojego wykresu, tak jak w powyższym przykładzie. (Adjacency_list: http://www.boost.org/doc/libs/1_50_0/libs/graph/doc/adjacency_list.html)

Answer 1

O pytań w komentarzach:

1. Zgodnie z komentarzem w źródłowego przykładu VC++ ma pewne problemy z named parameter mechanism used. Dlatego założyłbym, że obie gałęzie działają w zasadzie tak samo, a wersja VC++ jest po prostu bardziej gadatliwa (nie zanurkowałem w nią wystarczająco długo, aby być w 100% pewnym).
2. A property_map mapuje wierzchołki/krawędzie na dodatkowe dane powiązane z określonym wierzchołkiem/krawędzią. Na przykład. weightmap w przykładzie wiąże wagę (koszt podróży) z każdą krawędzią.

3. The predecessor_map służy do rejestrowania ścieżki dla wszystkich wierzchołków (na każdy wierzchołek poprzednika na drodze od korzenia mamy). Co do tego, dlaczego jest potrzebna: Cóż, ta informacja jest czymś, co często ma nadzieję wyjść z algorytmu.

4. Parametry są wyraźnie wymienione w description. Zwróć uwagę na dwie wersje, jedną o nazwanych parametrach i jedną bez (później używaną w VC++).

teraz nieco krok po kroku kodu przykładzie podanym w the documentation (zauważ, że ja nigdy nie używane Boost.Graph, więc to nie ma gwarancji na poprawność, również ja tylko włączone odpowiednie części i pominięty #if dla 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])); 

Jak wspomniano w komentarzach osobiście uważam lemon bardziej intuicyjne w użyciu następnie Boost.Graph, więc może warto dać, że wygląd zamiast