Dijkstra最短路径算法：std::priority_queue与std::set的性能比较

Question

我希望了解这些容器在时间复杂度方面的主要区别。我尝试了以下三种Dijkstra算法的实现：

1- 使用简单数组作为队列

2- 使用STL优先队列

3- 使用STL集合

我测试的图形相当大，包含超过150000个顶点，都是有向的，边的权重都是正数。

我得到的结果如下：

1- 用数组算法非常慢——这是预期的；

2- 使用STL优先队列比数组运行快得多——这也是预期的；

3- 使用STL集合算法运行速度非常快，我说的是比优先队列快上几百倍——我没有预料到会有这么大的性能差异……

知道std::priority_queue和std::set都是存储元素的数据容器，它们的插入复杂度基本相同为O(log n)，我不理解它们之间的这种巨大性能差异。你有关于这个的任何解释吗？

感谢您的帮助，

编辑：

这是我的实现摘要：

使用std::set:

unsigned int Graphe::dijkstra(size_t p_source, size_t p_destination) const {

....


set<pair<int, size_t>> set_vertices;


vector<unsigned int> distance(listAdj.size(),
        numeric_limits<unsigned int>::max());


vector < size_t
        > predecessor(listAdj.size(),
                numeric_limits < size_t > ::max());


distance[p_source] = 0;
set_vertices.insert( { 0, p_source });


while (!set_vertices.empty()) {

    unsigned int u = set_vertices.begin()->second;


    if (u == p_destination) {
        break;
    }

    set_vertices.erase( { distance[u],
            u });


    for (auto itr = listAdj[u].begin();
            itr != listAdj[u].end(); ++itr) {


        int v = itr->destination;
        int weigth = itr->weigth;


        if (distance[v]
                > distance[u] + weigth) {


            if (distance[v]
                    != numeric_limits<unsigned int>::max()) {
                set_vertices.erase(
                        set_vertices.find(
                                make_pair(distance[v],
                                        v)));
            }

            distance[v] = distance[u] + weigth;

            set_vertices.insert( { distance[v],
                    v });

            predecessor[v] = u;
        }
    }
}

....

return distance[p_destination];}

同时使用 priority_queue：

unsigned int Graphe::dijkstra(size_t p_source, size_t p_destination) const {

...

typedef pair<size_t, int> newpair;

priority_queue<newpair, vector<newpair>, greater<newpair> > PQ;

vector<unsigned int> distance(listAdj.size(),
        numeric_limits<unsigned int>::max());


vector < size_t
        > predecessor(listAdj.size(),
                numeric_limits < size_t > ::max());


distance[p_source] = 0;
PQ.push(make_pair(p_source, 0));

while (!PQ.empty()) {


    unsigned int u = PQ.top().first;


    if (u == p_destination) {
        break;
    }

    PQ.pop();


    for (auto itr = listAdj[u].begin();
            itr != listAdj[u].end(); ++itr) {


        int v = itr->destination;
        int weigth = itr->weigth;


        if (distance[v]
                > distance[u] + weigth) {

            distance[v] = distance[u] + weigth;

            PQ.push(
                    make_pair(v, distance[v]));

            predecessor[v] = u;
        }
    }
}
...

return distance[p_destination];}

- Merouane Benthameur

---

你的实现是否正确？ - Lucero

是的，我相信它是正确的，在这三个实现中我得到了相同的输出（相同的路径查找）。除了第三个实现的运行时间非常快。 - Merouane Benthameur

展示你的实现。 - DAle

使用priority_queue和set时，更新顶点距离步骤可能会导致巨大的差异。您可以使用set轻松更新距离，但是如果不添加相同的顶点多次并具有不同的距离，则无法使用priority_queue进行更新。 - DAle

是的，很有道理，这也是我的假设，因为 priority_queue 的巨大损失发生在队列内第一个元素的 弹出 步骤，它需要 O(log(size_queue)) 的复杂度。 - Merouane Benthameur

Answer 1

SKIP

您在优先队列中做了很多重复工作。

您正在进行双重插入，因为不能修改或删除。这是正常和必要的，因为您无法这样做。

但是，当那些旧值从队列中出来时，您需要“跳过 while 循环的这次迭代”。

可以尝试以下代码：

if (PQ.top().second != distance[PQ.top().first]) continue;  // It's stale! SKIP!!

- Oliver Schönrock

---

什么是过时节点？这个说法正确吗：当我们处理节点X的邻居时，我们可能会发现到节点Z的距离小于已记录的距离。因此，我们更新记录的距离并将新的{节点Z，到Z的距离}推入PQ。但是，在未来的迭代中处理该节点之前，我们处理节点Y的邻居并发现到Z的距离小于刚刚记录的距离；因此，我们再次更新记录并将{节点Z，到Z的距离}推入队列。但是，先前添加的项**仍然在PQ中。它已经过时了。 - Justin

因此，为了达到最优化，我们应该只处理来自PQ的项{节点i，距离i}，其中距离i等于记录的距离数组中的距离（即distance [i]）。这个记录的距离数组包含到目前为止找到的最新（最短）距离。请让我知道我的理解是否正确。我认为这与此处评论中讨论的内容相同：https://cs.stackexchange.com/a/118406/141696 - Justin

是的，这一切都是正确的。除了你不需要检查 PQ.top().second > dist[PQ.top().first]，只需要使用 != 即可，而且通常会稍微快一些。这是因为队列中过期的项目只能是 >，它们不能是 <，因为队列排序的方式和发现并插入新的更短路径的方式的本质。是的，你链接中的讨论也是关于同样的事情。 - Oliver Schönrock

Answer 2

std::priority_queue 的底层数据结构是最大堆，而对于 std::set 则是自平衡二叉搜索树——基本上是 C++ 中的红黑树。因此，它们都确保了插入、删除和更新操作的 O(logn) 时间复杂度。

但是，正如我所提到的，std::set 的平衡二叉搜索树会自动平衡以保持其高度为节点数的对数，这确保了无论插入顺序或任何操作后，查询复杂度都是对数级别的。而 std::priority_queue 则不是自平衡的，根据插入顺序可能会非常扁平。虽然自平衡也有其代价，以及在移除顶部后进行堆化的代价，但我认为这就是性能提升的原因。

希望这可以帮助你！

- Kaidul

---

堆是一棵完全二叉树，它不能根据插入顺序变得“非常扁平”。 - DAle