std::vector elements are normally initialized to zero when they are created. push() does ignore the values; push_or_update() needs them to be correct.
But I am calling push() on every vertex first, right (so the automatic initialization shouldn't ever be seen by the update() )? And you are saying the queue expects them to be initialized to (size_t)(-1)? I tried initializing it explicitly: http://ideone.com/OgWF6 but the output is still really wacky: There are 0 items in the queue. Original priority for 0, 0 744 Index added: 0 Index added caller: 0 Original priority for 1, 0 562 Index added: 1 Index added caller: 1 Original priority for 0, 1 824 Index added: 2 Index added caller: 0 (THIS 0 SEEMS WRONG) Original priority for 1, 1 156 Index added: 3 Index added caller: 3 There are 4 items in the queue. New priority for 0, 0 890 New priority for 1, 0 851 New priority for 0, 1 55 New priority for 1, 1 284 There are 4 items in the queue. vertex: 0 0 priority: 890 indexInHeap: 0 (THIS 0 SEEMS WRONG) vertex: 1 0 priority: 851 indexInHeap: 0 (THIS 0 SEEMS WRONG) vertex: 1 1 priority: 284 indexInHeap: 0 (THIS 0 SEEMS WRONG) vertex: 0 1 priority: 55 indexInHeap: 0 (THIS 0 SEEMS WRONG) Sorry to be a pain, but I've stepped though all of this and can't figure out why the index_in_heap map isn't returning the same values inside and outside the loop, and zero for every vertex at the end of the program? Thanks for your help, David