我已经实现了 Bellman-Ford 算法来解决问题（用图），但是这个解决方案太慢了，所以我用堆 (std::set) 替换了 Bellman-Ford 的队列，所以最短的解决方案会更快找到路径。 （某种程度上接近 Dijkstra 算法）
现在，我在堆中插入节点编号，因此默认的 std::set 将使用节点的编号而不是成本对节点进行排序。一切都很好，算法给出了正确的答案。
如果我为 std::set 实现自定义比较函数，以便节点将按距离而不是按数量排序，则算法不再提供到其余节点的最短距离。
这是我的比较函数：
struct cmp{
bool operator() (const int &a,const int &b) const{
return (d[Q][a] < d[Q][b] );
}
};
set <int,cmp> q;
因此，作为 BF 算法，该算法会一直运行，直到无法做出任何改进为止。比较函数是否可以以某种方式“混乱”std::set，因为这是我能理解为什么添加此比较函数会给出错误答案的唯一原因...
我的意思是，如果节点完全随机，它为什么会起作用订单，但如果按成本订购则不起作用......
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...
发布评论
评论（1）
据我记得 Bellman-Ford 算法 它更新了节点。因此，使用权重作为
std::set的键并不容易：std::set中的搜索不会成功如果您刚刚更改了距离，请找到相应的值。追求这个方向你需要做的是删除要更新的节点，更改节点的距离，然后重新插入它。另请注意，std::set中的对象需要具有唯一的键：插入已存在的键将会失败。您说您正在使用 更有效。
std::set作为某种优先级队列。您看过std::priority_queue吗？这正是这样做的，但它往往比使用 std::setstd::priority_queue的问题是您无法更改对象优先级：您只能访问当前的顶部。很久以前，我创建了一个优先级队列（堆）集合，其中包括允许更改对象优先级的优先级队列版本（它们是 Boost 初始库的一部分，但从未通过审核过程）。我不知道你如何使用优先级队列，因此我不知道这是否是合理的方向。也就是说，我不明白为什么您想要为 Bellman-Ford 算法使用
std::set。我的理解是，该算法重复遍历图表并用新的最短距离更新节点。您是否看过 Boost 对 贝尔曼-福特算法？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 thestd::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 instd::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 atstd::priority_queue<T>? This is doing exactly this but it tends to be more efficient than using astd::set<T>. The problem withstd::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?