1

我已经实现了一个 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，因为这是我明白为什么添加这个比较函数会给出错误答案的唯一原因......

我的意思是，如果节点的顺序完全随机，为什么它会起作用，但如果它们按成本排序则不起作用......

4

1 回答 1

2

据我记得Bellman-Ford 算法，它会更新节点的距离。因此，使用权重作为键std::set<T>并不容易：std::set<T>如果您只是更改距离，则在 中的搜索不会找到相应的值。追求这个方向你需要做的是移除要更新的节点，改变节点的距离，然后重新插入。另请注意，std::set<T>需要具有唯一键的对象：插入已存在的键将失败。

您说您使用的std::set<int>是某种优先级队列。你看过了std::priority_queue<T>吗？这正是这样做的，但它往往比使用std::set<T>. 问题std::priority_queue<T>在于您无法更改对象优先级：您只能访问当前顶部。很久以前，我创建了一个优先级队列（堆）集合，其中包括允许更改对象优先级的优先级队列版本（它们是 Boost 初始库的一部分，但它们从未通过审查过程）。我不知道您如何使用优先级队列，因此我不知道这是否是合理的研究方向。

也就是说，我不明白为什么你会想要一个std::set<T>贝尔曼福特算法。我的理解是，该算法反复遍历图形并以新的最短距离更新节点。你看过Boost 的Bellman -Ford 算法实现吗？

于 2012-02-12T19:17:07.743 回答