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

Subject: Re: [boost] [graph] interest in resumable dijkstra?
From: Alex Hagen-Zanker (ahh34_at_[hidden])
Date: 2012-08-10 17:28:02

On 10/08/2012 21:12, Jeremiah Willcock wrote:
> 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.

No that's not how the algorithm works. The Dijkstra algorithm is applied 
on the full transport network and the resulting tree forms the initial 
DAG for the rest of the 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?

Yes, I also think both methods will work. I know mine is working and 
yours is a generalization as far as I can see.

Yes, I use serialization to save on memory usage.