From: Jens Theisen (jens-theisen-tmp01_at_[hidden])
Date: 2006-08-10 15:27:34
Doug Gregor wrote:
>>I once had the idea of using boost::graph to implement a diffing
>>algorithm by applying dikstra to the edit graph of two sequences
>>(that's
>>the popular way of doing this I think).
>
> I didn't know that. Very interesting!
Well, sorry, I meant viewing it as finding the shortest path in the edit
graph is popular. Rooting in on dijkstra itself probably isn't.
> There is a "no_init" version of Dijkstra's algorithm that skips the
> initialization entirely. Of course, the user would be responsible for
> initializing property map values for vertices on demand, e.g., in
> examine_edge. I've seen the no_init form of Dijkstra's used for other
> "implicit" graphs, which have similar properties to the one you
> describe.
That doesn't help very much because even that is initialising it's
relaxed_heap with num_vertices(g), so the algorithm will linear in the
number of it's vertices anyway. You really want to drop the
VertexListGraph requirement for the no_init version (or yet another one).
Jens