dijkstra_shortest_paths with undirectedS example

21 Apr 2003

      Hello,

I am new to BGL, I was trying to test dijkstra_shortest_paths() with 
undirectedS, the result is not what I wanted, anyone giving help? 
Thanks, source code like dijkstra-example.cpp in the graph/example.

int
main(int, char *[])
{
  typedef adjacency_list < listS, vecS, undirectedS,
    no_property, property < edge_weight_t, double > > graph_t;
  typedef graph_traits < graph_t >::vertex_descriptor 
vertex_descriptor;
  typedef graph_traits < graph_t >::edge_descriptor edge_descriptor;
  typedef std::pair<int, int> Edge;

  const int num_nodes = 3;
  Edge edge_array[] = { Edge(0, 1),Edge(1, 2), Edge(2, 0) };
  double weights[] = {2.0, 1.0, 1.0};
  int num_arcs = sizeof(edge_array) / sizeof(Edge);//

#if defined(BOOST_MSVC) && BOOST_MSVC <= 1300
  graph_t g(num_nodes);
  property_map<graph_t, edge_weight_t>::type weightmap = get
(edge_weight, g);
  for (std::size_t j = 0; j < num_arcs; ++j) {
    edge_descriptor e;
	bool inserted;
    tie(e, inserted) = add_edge(edge_array[j].first, edge_array
[j].second, g);
    weightmap[e] = weights[j];
  }
#else
  graph_t g(edge_array, edge_array + num_arcs, weights, num_nodes);
  property_map<graph_t, edge_weight_t>::type weightmap = get
(edge_weight, g);
#endif
  std::vector<vertex_descriptor> pred(num_vertices(g));
  std::vector<double> d(num_vertices(g));
  vertex_descriptor s = vertex(0, g);

#if defined(BOOST_MSVC) && BOOST_MSVC <= 1300
  // VC++ has trouble with the named parameters mechanism
  property_map<graph_t, vertex_index_t>::type indexmap = get
(vertex_index, g);
  dijkstra_shortest_paths(g, s, &pred[0], &d[0], weightmap, indexmap, 
                          std::less<double>(), closed_plus<double>(), 
                          std::numeric_limits<double>::max(), 0,
                          default_dijkstra_visitor());
#else 
  dijkstra_shortest_paths(g, s, predecessor_map(&p[0]).distance_map(&d
[0]));
#endif

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

  std::cout << "min paths tree" << std::endl;
  adjacency_list<> tree(num_nodes);

  for(tie(vi,vend) = vertices(g); vi != vend; ++vi)
    if (*vi != pred[*vi])
      add_edge(pred[*vi], *vi, tree);

  print_graph(tree);

  std::cout << std::endl;

  return EXIT_SUCCESS;
}

The result is :
distances and parents:
distance(0) = 0, parent(0) = 0
distance(1) = 2, parent(1) = 0
distance(0) = 1, parent(2) = 0
min paths tree
0 -> 1 2
1 ->
2 ->

I think the correct one should be:
distances and parents:
distance(0) = 0, parent(0) = 0
distance(1) = 2, parent(1) = 2
distance(2) = 1, parent(2) = 0
min paths tree
0 -> 1 
1 -> 2
2 ->

Any idea what is wrong? thanks!

dijkstra_shortest_paths with undirectedS example

jfw1000