[Boost-users] dijkstra_shortest_paths and vertex_index

From: Steve Buchko (stevebu_at_[hidden])
Date: 2004-10-15 18:55:30

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.

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?

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?

Thanks,
steve