我已经实现了 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，因为这是我能理解为什么添加此比较函数会给出错误答案的唯一原因...
我的意思是，如果节点是完全随机的顺序，为什么它会工作，但如果它们按成本排序就不会工作...
最佳答案
据我所知 Bellman-Ford algorithm它更新节点的距离。因此，使用权重作为 std::set<T> 的关键。不容易工作:在 std::set<T> 中搜索如果您只是更改距离，将找不到相应的值。按照这个方向，您需要做的是删除要更新的节点，更改节点的距离，然后重新插入。另请注意 std::set<T> 中的对象需要有一个唯一的 key :插入一个已经存在的 key 将失败。
你说你正在使用 std::set<int>作为某种优先级队列。你看过std::priority_queue<T>了吗？ ？这正是这样做的，但它往往比使用 std::set<T> 更有效。 . std::priority_queue<T> 的问题是你不能改变一个对象的优先级:你只能访问当前的顶部。很久以前，我创建了一个优先级队列(堆)集合，其中包括允许更改对象优先级的优先级队列版本(它们是 Boost 初始库的一部分，但它们从未通过审查过程)。我不知道您如何使用优先级队列，因此我不知道这是否是一个合理的观察方向。
就是说，我不明白你为什么想要一个 std::set<T>无论如何，对于 Bellman-Ford 算法。我的理解是该算法反复遍历图形并使用新的最短距离更新节点。你看过Boost's了吗？实现 Bellman-Ford algorithm ？
关于c++ - 带有堆的 Bellman-Ford 不适用于自定义比较功能，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/9251523/