Re: [boost] [graph] interest in resumable dijkstra?

Subject: Re: [boost] [graph] interest in resumable dijkstra?
From: Jeremiah Willcock (jewillco_at_[hidden])
Date: 2012-08-10 16:12:27

On Thu, 10 Aug 2012, Alex Hagen-Zanker wrote:

> On Aug 9 2012, Jeremiah Willcock wrote:
>
>
>> OK.  It looks like that algorithm is using longest paths (in DAGs) as well 
>> as shortest paths.  Is that also something that you're doing?
>
> Yes, but that part of the calculation does not require resumability. It is 
> from scratch each iteration. It is based on a topological sort and does not 
> use dijkstra shortest paths.

Couldn't you do shortest paths in the same topological sort sweep?  That 
would probably be faster than Dijkstra's algorithm.

>> Do you just use this to interleave computations, with the maps used to 
>> restart a shortest path search from where it left off, or are you 
>> manipulating the maps in some other way?
>
> I just restart where I was left. The only thing that changes is the 
> termination criterion. (e.g. the weights on the edges remain the same)

OK.  I think either your model for suspension or the algorithm object 
model (what I had proposed) will work for that case.  Do you need 
serialization to save on memory usage?

-- Jeremiah Willcock