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

问题描述

我想了解这些容器在时间复杂度方面的主要区别.我已经尝试了 3 种 Dijkstra 算法的实现，如下所述:

I would like to understand the main difference of these containers regarding their time complexity. I've tried 3 implementations of Dijkstra algorithm as described below:

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

1- with a simple array used as queue

2- 使用 STL priority_queue

2- with STL priority_queue

3- 设置 STL

我测试过的图很大，它包含超过 150000 个顶点，并且所有的边的权重都是正的.

the graph I've tested is quite big, it contains more than 150000 vertices, oriented and all the weight of the edges are positive.

我得到的结果如下:

1 - 使用数组算法很慢 --> 这是预期的

1 - with array the algorithm is pretty slow --> which is expected

2 - 使用 STL priority_queue，算法运行速度比数组快得多 --> 这也是预期的

2 - with STL priority_queue the algorithm run a lot faster than the array --> which is also expected

3 - 使用 STL 设置算法运行速度非常快，我说的是比 priority_queue 快 100 倍 --> 我没想到会看到如此巨大的性能...

3 - with STL set the algorithm run incredibly fast, I'm talking about couple 100 times faster than the priority_queue --> I didn't expect to see this huge performance...

知道 std::priority_queue 和 std::set 是存储元素的数据容器，并且两者具有基本相同的插入复杂度 O(log n)，我不明白它们之间的巨大性能差异.你对此有什么解释吗?

knowing that the std::priority_queue and std::set are data containers that store elements and both have basically the same insertion complexity O(log n), I don't understand this big performance difference between them. Have you any explanation about this?

感谢您的帮助，

已这是我的实现的摘要:

使用 std::set:

with 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:

and with 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];}

推荐答案

SKIP

优先级队列让你的工作加倍.

SKIP

You are doubling up on the work really badly with the priority queue.

您正在重复插入队列，因为您无法修改或删除.这是正常和必要的，因为你不能.

You are double inserting into the queue, because you can't modify or delete. That's normal and necessary, because you can't.

但是当那些旧值从队列中出来时，您需要跳过 while 循环的那个迭代".

but then when those old values come out of the queue you need to "skip that iteration of the while loop".

类似于:

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

这篇关于std::priority_queue 与 std::set 的 Dijkstra 最短路径算法性能的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！