[Boost-users] [astar search] Computation time for large graph

Subject: [Boost-users] [astar search] Computation time for large graph
From: Yann-Hervé Hellouvry (yannherve.hellouvry_at_[hidden])
Date: 2013-01-09 10:11:40

Hi,

I try to use the "astar-cities" example but for graph of about 10000 nodes
and edges (which are weighted) in order to find the fastest path between
two random nodes... and I want to do it several times. I encountered very
large computation time : about 4 min to perform 100 searches.

Is it supposed to be slow for large graph?
My machine is not very powerful but I think I've missed something...Is
there ways to optimize? Can it be a problem from the weighted edges or from
the heuristic distance ?

my astar_search function call is :

boost::astar_search(m_g,
                    vertexStart,
                    heuristicDistance,
                    boost::predecessor_map(&p[0])
                    .distance_map(&d[0])
                    .visitor(astarVisitor)
                    );
with m_g my graph which is a:
typedef boost::adjacency_list<boost::listS, boost::vecS,
boost::bidirectionalS, VertexProperties,
boost::property<boost::edge_weight_t, float> > my_graph;

heuristicDistance : same as the example (a simple euclidian distance)
astarVisitor : same as the example

any help is appreciated !
Thanks,

Happy new year btw,
YH