Boost logo

Boost :

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

Boost list run by bdawes at, gregod at, cpdaniel at, john at