Dijkstra shortest path
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.
AMDG dwaem wrote:
int weight[] = {1, 1, 2, 2, 3, 4, 3, 4, 5, 6, 7};
<snip>
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.
You're not using the weight array anywhere, so you get the default weight of 0 for every edge. In Christ, Steven Watanabe
Steven Watanabe-4 wrote:
AMDG
dwaem wrote:
int weight[] = {1, 1, 2, 2, 3, 4, 3, 4, 5, 6, 7};
<snip>
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.
You're not using the weight array anywhere, so you get the default weight of 0 for every edge.
In Christ, Steven Watanabe
_______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users
Yes this is my obviouse oversight. But now when I have founded shortest path from node A to node B. How to display full path from A to B, not only parent of the last node. -- View this message in context: http://www.nabble.com/Dijkstra-shortest-path-tp22626827p22662345.html Sent from the Boost - Users mailing list archive at Nabble.com.
participants (2)
-
dwaem
-
Steven Watanabe