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

我已经在C++ from this page中复制了dijkstra的算法，并对其进行了修改以适合我的图形表示形式类。基本上，我只用自己的结构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);
    }
};

但是，我必须实现operator true(所以e2.weight >= weight实际上可能比e2.weight大大于weight)，则较长的语句返回vertex < e2.vertex。但是顶点数没有出现在Dijkstra算法的定义中。

那么，仅使用第二个return语句，程序如何正常工作？

最佳答案

改写正确的return语句:

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);

(由于与第一个条件发生短路，
所以我希望我的体重更小....或者如果相等，则顶点更小。

编辑(误解了原来为什么措辞失败):
标准套装要求严格的订购。

当您插入图形边缘时，这些边缘的权重可以相同-因此，权重本身并不是边缘的唯一标识符，因此，它与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();

关于c++ - Dijkstra的算法-优先级队列中的比较，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/24048505/