Re: [Boost-users] [BGL] dijkstra_shortest_path fails to call initialize_vertex

From: Doug Gregor (dgregor_at_[hidden])
Date: 2006-08-10 09:39:32

On Aug 9, 2006, at 5:20 PM, Jens Theisen wrote:
> By the way, isn't it rather undesirable that initialisation is done
> prior to the algorithm, rather than on-demand?
>
> 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!

> But you don't really want to
> build that graph, or you'll end up with quadratic complexity in any
> case, whereas you can have something like O(kn) where n is the  
> length of
> both sequences and k is the number of "edits" in a shortest ed-script
> (if we take the priority queue lookup as constant).

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.

        Doug