[Boost-users] how to use no_init dijkstra

Subject: [Boost-users] how to use no_init dijkstra
From: Fletcher Foti (fscottfoti_at_[hidden])
Date: 2011-05-11 18:40:21

I'm really surprised I can't find information on this - I feel like
I'm doing something very basic...

What I want is all the nodes within a certain distance in the graph.
I have a graph of half a million nodes and will only be visiting 20 or
so - if you're curious, I have a graph of the street network in the
Bay Area and will be looking at only those nodes within walking
distance.

So I read elsewhere that I need to inherit from
default_dijkstra_visitor and throw an exception when I finalize a
vertex beyond my search radius.  I think I have this working.

Now my problem is that I have to do this search many, many times -
performance is very important - and I don't want to initialize the
values for a half a million nodes when I'm only going to visit 20.  I
therefore want to use a std::map to store distances, and I want a key
missing from that map to indicate an unvisited node, right?  I also
want to use dijkstra_shortest_path_no_init so as to skip
initialization, but it's very hard to find documentation on this.

I could post all my code here, but I'm not yet sure if that's the most
efficient way to get my question answered.  How does the no_init
function work?  Why doesn't it take a value for infinity?  I feel like
I need to pass DistanceMap.end() as my value for infinity so that a
node not in the distance map looks like an unvisited node.  Can anyone
explain to me in words what I the no_init function expects me to pass
to it?

Thanks in advance!
Fletcher