If the graph is acyclic -> it is a tree -> there is 1 and only 1 path between any two vertices (consequently, it is both shortest and longest). So you might as well perform breadth-first search from a starting vertex to get all paths and distances to other vertices. BFS complexity is O(|A|) where |A| is the number of edges in the graph.
So, how "zvrba@globalnet.hr" point out absolutly correctly the problem could be solved using BFS (in linear time with respect to edges number), with the following visitor //////////////////code//////////////////// #include <boost/graph/adjacency_list.hpp> #include <boost/graph/breadth_first_search.hpp> using namespace boost; template < typename DistanceMap > class bfs_distance_visitor : public default_bfs_visitor { typedef typename property_traits < DistanceMap >::value_type T; public: bfs_distance_visitor(DistanceMap dmap) : m_distances(dmap) { } template <typename vertex_descriptor, typename Graph> void initialize_vertex(vertex_descriptor v, Graph& g) { m_distances[v] = 0; } template < typename Edge, typename Graph > void tree_edge(Edge e, Graph& g) { put(m_distances, target(e, g), m_distances[source(e,g)] + get(edge_weight, g, e)); } DistanceMap m_distances; }; typedef adjacency_list <listS, vecS, undirectedS, no_property, property<edge_weight_t, double> > graph_t; typedef graph_traits<graph_t>::vertex_descriptor vertex_descriptor_t; struct ltvertex { bool operator()(vertex_descriptor_t v1, vertex_descriptor_t v2) const { return unsigned(v1) < unsigned(v2); } }; template <typename TValue> struct vertex_external_property_map { typedef std::map<vertex_descriptor_t, TValue, ltvertex> property_map_type; }; typedef vertex_external_property_map<double>::property_map_type distance_map_t; int _tmain(int argc, _TCHAR* argv[]) { graph_t g; typedef associative_property_map<distance_map_t> T; T dmap; bfs_distance_visitor<associative_property_map<distance_map_t> > vis(dmap); //Now it would be good to read graph breadth_first_search(g, vertex(0, g), visitor(vis)); return 0; } ///////////////////////////////////////////////////////////////////////////// If it doesn't work then I don't know who wrote it Ну привет, --Дима