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

Subject: Re: [Boost-users] [astar search] Computation time for large graph
From: Jeremiah Willcock (jewillco_at_[hidden])
Date: 2013-01-09 11:09:21

On Wed, 9 Jan 2013, Yann-Hervé Hellouvry wrote:

> 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 ?

One issue could be that your graph uses listS as out edge container, but 
that shouldn't cause the search to be as slow as you're experiencing.  Are 
you sure your compiler's optimization is enabled and that NDEBUG is 
defined?

-- Jeremiah Willcock