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