Hi Florian,
Do you have a few lines of code you could share that show the bug you're seeing? I'd like to trace through and see what's going on...
... sure! I inlined some test code for basic operations. Depending on the activated parts (*A* - *D*) I see all sorts of strange behaviour. Sorting could be just wrong, some elements are shown more than once (somewhere within the sequence, or like repeating the largest element in the end, as below). In some cases (I think when updating first or last elements of w) the program hangs. In the beginning I tried to push vertices to the heap when I assign a path cost to them, instead of pushing all vertices (having infinite path cost then anyways) before I start the relaxing stuff -- doing this I saw the same kind of behaviour. The output of the code below executing, e.g. *A* only, results in: showing the *un-sorted* vector 10 9 8 7 6 5 4 3 2 1 smallest element w[9] == 1 call pop changing w[5] == 5 to -1, update Q showing the *sorted* vector -1 2 3 4 2 3 10 10 10 Any help would be appreciated! Thanks in advance Florian // filling a vector w with n descending numbers int N = 10; vector<float> w; for (int t = 0; t < N; ++t) w.push_back(N-t); cout << "showing the *un-sorted* vector" << endl; for (int i = 0; i < N; ++i) cout << w[i] << endl; // declaring the head (taken from an example on the web) typedef indirect_cmp<float*,std::less<float> > ICmp; ICmp cmp(&w[0], std::less<float>()); fibonacci_heap<int, ICmp> Q(N, cmp); // pushing all of w's indices to the Q for (int i = 0; i < N; ++i) Q.push(i); // top/pop smallest element (this is the last one in w) cout << "smallest element w[" << Q.top() << "] == " << w[Q.top()] << endl; cout << "call pop" << endl; Q.pop(); // change some elements in w and update Q // *A* cout << "changing w[5] == " << w[5] << " to -1, update Q" << endl; w[5] = -1.; Q.update(5); // *B* // cout << "changing w[8] == " << w[7] << " to -7, update Q" << endl; // w[7] = -7.; // Q.update(7); // *C* // cout << "changing w[3] == " << w[3] << " to -5, update Q" << endl; // w[3] = -5.; // Q.update(3); // *D* // cout << "changing w[0] == " << w[0] << " to -5, update Q" << endl; // w[0] = -5.; // Q.update(0); // output the rest of w, sorted cout << "showing the *sorted* vector" << endl; while (Q.size() > 0) { cout << w[Q.top()] << endl; Q.pop(); }