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

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