Hi there,
This unreviewed code has been languishing in Boost pending for years. I was going to remove it, but hadn't done so yet. I see that Aaron Windsor committed a fix to the RC_1_34_0 branch of CVS a few months ago: are you using that Fibonacci heap? I've just put Aaron's fix into CVS HEAD as well; an update might fix the problem you are seeing.
and thanks a lot for your answer! I looked at the new version you uploaded and it seems identical to the one I used before -- but, if I get you right, it is not the best idea to use the fibonacci heap, anyways. At the moment I search an unsorted linear list O(|V|) times -- so I would benefit from every other structure ... what would you suggest? Some standard binary heap? The mutable_queue looked good to me but this one is pending, too ...
Thanks again Florian