c++ - Dijkstra 算法 - 优先队列中的比较

Question

我用 C++ 复制了 dijkstra 的算法 from this page并修改它以适合我的图形表示类。基本上，我只更换了 std::pair作为 std::set 的模板参数通过我自己的结构edge :

struct edge
{
    int vertex;
    unsigned long weight;

    edge(int v = 0, unsigned long wt = 0) : vertex(v), weight(wt) { }

    bool operator<(const edge& e2) const
    {
        //return weight < e2.weight;
        return weight < e2.weight || ((e2.weight >= weight) && vertex < e2.vertex);
    }
};

但是，我必须实现类似于 std::pair 中的运算符<。当我使用注释返回语句时，输出是错误的。但是较长的语句返回 true如果e2.weight >= weight (所以 e2.weight 实际上可能大于 weight )只要 vertex < e2.vertex .但是顶点号没有出现在Dijkstra算法的定义中。

那么程序为什么只用第二个 return 语句就可以正常工作呢？

Answer 1

改写正确的返回语句:

return (this->weight < e2.weight) || ((this->weight <= e2.weight) && this->vertex < e2.vertex);

相当于:

return (this->weight < e2.weight) || ((this->weight == e2.weight) && this->vertex < e2.vertex);

(<= 由于第一个条件的短路而分解为 ==)

所以我希望我的重量更小......或者如果相等，顶点更小。

编辑(误解了原文why does it fail phrasing):标准集需要严格排序....

当您插入图形边时，这些边的权重可以相同 - 因此，单独的权重并不是边的唯一标识符，因此它与 Djikstra 的逻辑排序机制无关 - 它是保持所有边缘而不在集合中相互覆盖的一种方式。

对于更明显的失败案例，请尝试使用 op<:

的两个定义来执行此操作

//int verticeIdx[4] = {0, 1, 2, 3} 
int constWeight = 3;
edge myEdge(0, constWeight), myNewEdge(1, constWeight);
std::set<edge> edges;
edges.insert(myEdge);
edges.insert(myNewEdge);
std::cout << edges.size();