[Boost-users] Dijkstra shortest path

Subject: [Boost-users] Dijkstra shortest path
From: dwaem (dwaem_at_[hidden])
Date: 2009-03-20 15:03:08

Hi
I made a little change to example from manual which search shortest path
http://www.boost.org/doc/libs/1_37_0/libs/graph/example/dijkstra-example.cpp
http://www.boost.org/doc/libs/1_37_0/libs/graph/example/dijkstra-example.cpp 
by adding add_edge function but is seams to give incorect results

#include <boost/config.hpp>

#include <algorithm>
#include <vector>
#include <utility>
#include <iostream>

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/reverse_graph.hpp>
#include <boost/graph/graph_utility.hpp>
#include <boost/graph/dijkstra_shortest_paths.hpp>
#include <boost/graph/graph_traits.hpp>
#include <boost/graph/adjacency_list.hpp>
using namespace boost;

int main() {
        typedef adjacency_list	< vecS, vecS, bidirectionalS, no_property, property
< edge_weight_t, int > > graph;
        typedef graph_traits		< graph >::vertex_descriptor vertex_descriptor;
        typedef graph_traits < graph >::edge_descriptor edge_descriptor;
        
        graph G(5);
        enum nodes { A, B, C, D, E };

        add_edge(A, E, G);
        add_edge(B, E, G);
        add_edge(C, E, G);
        add_edge(A, B, G);
        add_edge(B, D, G);
        add_edge(B, A, G);
        add_edge(B, C, G);
        add_edge(C, A, G);
        add_edge(C, D, G);
        add_edge(D, A, G);
        add_edge(D, B, G);
        
        int weight[] = {1, 1, 2, 2, 3, 4, 3, 4, 5, 6, 7};

        
             char name[] = "ABCDE";
        std::cout << "\n";

        vertex_descriptor s = vertex(C, G);
        property_map<graph, edge_weight_t>::type weightmap = get(edge_weight, G);
        std::vector<vertex_descriptor> p(num_vertices(G));
        std::vector<int> d(num_vertices(G));
        dijkstra_shortest_paths(G, s, predecessor_map(&p[0]).distance_map(&d[0]));

        std::cout << "distances and parents:" << std::endl;
   graph_traits < graph >::vertex_iterator vi, vend;
        for (tie(vi, vend) = vertices(G); vi != vend; ++vi){
                std::cout << "distance(" << name[*vi] << ") = " << d[*vi] << ", ";
                std::cout << "parent(" << name[*vi] << ") = " << name[p[*vi]] <<
std::endl;
        }
        
        std::cout << std::endl;
}

it shows 
distances and parents:
distance(A) = 0, parent(A) = C
distance(B) = 0, parent(B) = A
distance(C) = 0, parent(C) = C
distance(D) = 0, parent(D) = C
distance(E) = 0, parent(E) = C

which makes no sense. 

Marcin Matuszak
-- 
View this message in context: http://www.nabble.com/Dijkstra-shortest-path-tp22626827p22626827.html
Sent from the Boost - Users mailing list archive at Nabble.com.