Bellman-Ford with heap doesn't work with custom compare function

Question

I have implemented a Bellman-Ford algorithm to solve a problem (with a graph), but this solution was too slow, so I have replaced the Bellman-Ford's queue with a heap (std::set) , so the solution for the shortest path will be found faster. (somehow close do Dijkstra algorithm)

Now, I insert the node number in the heap, so the default std::set will sort the nodes using their number, not their cost. Everything is fine, and the algorithm gives the corect answers.

If I impelement a custom compare function for the std::set , so that the nodes will be sorted by their distance and not by their number the algorithm does no longer provide the shortest distance to the rest of the nodes.

This is my compare function:

 struct cmp{

    bool operator() (const int &a,const int &b) const{
        return (d[Q][a] < d[Q][b] );
    }
  };
 set <int,cmp> q;

So, being a BF algorithm, the algorithm runs until no improvement can be made. Can the compare function somehow "mess" the std::set, because this is the only reason I can see why adding this comparison function will give wrong answers...

I mean, why would it work if the nodes are in a completely random order but won't work if they are ordered by their cost...

Answer 1

As far as I recall the Bellman-Ford algorithm it updates the distance of the node. Thus, using the weight as the key for std::set<T> doesn't easily work: the search in the std::set<T> wouldn't find the respective value if you just changed the distance. What you would need to do pursue this direction is to remove the node to be updated, change the node's distance, and reinsert it afterwards. Please also note that objects in std::set<T> need to have a unique key: inserting a key which already exists will fail.

You said that you are using the std::set<int> as some sort of a priority queue. Did you have a look at std::priority_queue<T>? This is doing exactly this but it tends to be more efficient than using a std::set<T>. The problem with std::priority_queue<T> is that you can't change an objects priority: you have only access to the current top. A long time ago I had create a collection of priority queues (heaps) which included versions of the priority queues allowing changes to an object's priority (they were part of the initial libraries for Boost but they never made it through the review process). I don't know how you use your priority queue and thus I don't know whether this is reasonable direction to look at.

That said, I don't see why you would want to a std::set<T> for the Bellman-Ford algorithm anyway. My understanding is that the algorithm repeatedly goes through the graph and updates nodes with their new shortest distance. Did you have a look at Boost's implementation of the Bellman-Ford algorithm?