One thing in there that might be an issue is that you change the priorities of multiple vertices without running update() on the queue for each one separately. That may not work because the heap might get too far from satisfying the correct invariants.
I see what you're saying. Unfortunately that doesn't seem to do it either. In this demo: http://ideone.com/gfEMp I update(vertex) the queue after each priority is changed, but the output results in an unsorted (though correctly length 4) queue: There are 0 items in the queue. New priority for 0, 0 784 New priority for 1, 0 676 New priority for 0, 1 350 New priority for 1, 1 8 There are 4 items in the queue. The priority queue is: vertex: 0 0 priority: 784 vertex: 1 0 priority: 676 vertex: 0 1 priority: 350 vertex: 1 1 priority: 8 New priority for 0, 0 231 New priority for 1, 0 547 New priority for 0, 1 653 New priority for 1, 1 314 There are 4 items in the queue. The priority queue is: vertex: 0 0 priority: 231 vertex: 0 1 priority: 653 vertex: 1 0 priority: 547 vertex: 1 1 priority: 314
If that isn't the issue, could you please post or send me the exact, raw contents of the heap data (the internal vector) and the related property maps (IndexInHeap, priorities) before and after push_or_update operations that don't work correctly? The push_or_update function should do exactly what you are looking for, and so I'm surprised it isn't working correctly. Does the test at libs/graph/test/dijkstra_no_color_map_compare.cpp pass for you?
The test appears to pass (or at least the output is as follows): ------ Running dijkstra shortest paths test with 10 vertices and 500 edges **** no errors detected ------ I tried to output the index_in_heap, but it seems to be garbage (I just used get(index_in_heap, u)?): http://ideone.com/uj2lM produces: vertex: 1 1 priority: 234 indexInHeap: 4294967295 vertex: 0 1 priority: 828 indexInHeap: 0 vertex: 0 0 priority: 260 indexInHeap: 0 vertex: 1 0 priority: 46 indexInHeap: 0 The container/vector you mentioned seems to be private - how would I output its contents? Can you reproduce the unsorted result using the demo code? Thanks for your help, David