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

From: Douglas Gregor (doug.gregor_at_[hidden])
Date: 2006-08-14 13:08:06

On Aug 10, 2006, at 3:27 PM, Jens Theisen wrote:

> Doug Gregor wrote:
>> 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).

You are absolutely correct. I've opened up a bug report here:

        http://sourceforge.net/tracker/index.php? 
func=detail&aid=1540116&group_id=7586&atid=107586

I'll try to fix it in the near future, but it will likely take me a  
week or two before I get to it.

        Doug