Re: [Boost-users] dijkstra_shortest_paths and vertex_index

From: Jeremy Graham Siek (jsiek_at_[hidden])
Date: 2004-10-15 22:06:10

Hi Steve,

It does need to be sequential. The priority queue used inside 
Dijkstra's relies on that.

Cheers,
Jeremy

On Oct 15, 2004, at 6:55 PM, 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.
>
> 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
>
>
> _______________________________________________
> Boost-users mailing list
> Boost-users_at_[hidden]
> http://lists.boost.org/mailman/listinfo.cgi/boost-users
>
_______________________________________________
Jeremy Siek <jsiek_at_[hidden]>
http://www.osl.iu.edu/~jsiek
Ph.D. Candidate, Indiana University Bloomington
C++ Booster (http://www.boost.org)
_______________________________________________