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