Hello, Steve. --- Steve Buchko wrote:

I understand that when using listS to define vertices for a graph, I must also assign values to vertex_index before attempting to make use of dijkstra_shortest_paths.

You must assign a value to each vertex in the map a la put(get(vertex_index(), graph), vertex, value);

My question is, do the values assigned to vertex_index need to be sequential (i.e. 0 to n where n is the number of vertices in the graph), or can I assign any "random" integer to each vertex_index, as long as the values assigned are unique for each node?

The mapping must be 1-to-1, the values must range from 0 to n so that the priority queue it uses internally will function correctly, and the following relationship must hold: get(get(vertex_index(), graph), vertex(value, graph)) == value;

Does dijkstra_shortest_paths simply use the vertex_index as a unique identifier for the vertex, or is it using those indices to build an internal data structure such as an array or vector ... in which case using relatively large (or non-sequential) integers for vertex_index might be prohibitive from a memory or performance viewpoint?

Like I said before, dijkstra_shortest_paths builds a priority queue (actually a boost::mutable_queue) internally, wrapped around a std::vector. No idea about memory footprint, but as for performance, I have observed that dijkstra_shortest_paths does run slower when listS is chosen over vecS as the VertexList. HTH, Cromwell Enage _______________________________ Do you Yahoo!? Declare Yourself - Register online to vote today! http://vote.yahoo.com