为什么Dijkstra的算法使用堆(优先级队列)？

Question

我尝试在不使用优先级队列(Heap)的情况下在循环加权图上使用Djikstra算法,并且它有效.

然后我搜索谷歌"为什么我们需要一个优先级队列来实现这个？" 作为搜索的结果,我浏览了维基百科,在那里我了解到原始实现不使用优先级队列并在O(| V | 2)中运行,即V平方时间.

现在,如果我们只删除优先级队列并使用正常队列,则运行时间是线性的,即O(V + E).

请有人建议那么为什么我们需要优先队列？

Answer 1

我有完全相同的疑问,并找到了一个测试用例,其中没有priority_queue的算法不起作用.

假设我有一个Graph对象g,这是一种通过权重addEdge(a,b,w)从顶点a到顶点添加边的方法. bw

现在,让我定义以下图表: -

   Graph g 
   g.addEdge(0,1,5) ; 
   g.addEdge(1,3,1) ; 
   g.addEdge(0,2,2) ; 
   g.addEdge(2,1,1) ; 
   g.addEdge(2,3,7) ; 

现在,假设我们的队列按以下顺序包含节点.{0,1,2,3 } 因此,首先访问节点0,然后访问节点1.

此时,使用路径将dist b/w 0和3计算为6 0->1->3,并将1标记为已访问.

现在访问节点2并使用路径将dist b/w 0和1更新为值3 0->2->1,但由于节点1被标记为已访问,因此您无法更改距离b/w 0和3(使用最佳路径)( `0-> 2-> 1-> 3)是4.

因此,您的算法在不使用priority_queue的情况下失败.

它报告dist b/w 0和3为6,而实际上它应该是4.

现在,这是我用于实现算法的代码: -

        class Graph
    {
        public: 
            vector<int> nodes ; 
            vector<vector<pair<int,int> > > edges ; 
            void addNode() 
            {
                nodes.push_back(nodes.size()) ; 
                vector<pair<int,int> > temp ; edges.push_back(temp);
            }
            void addEdge(int n1, int n2, int w)
            {
                edges[n1].push_back(make_pair(n2,w)) ; 
            }
            pair<vector<int>, vector<int> > shortest(int source) // shortest path djkitra's
            {
                vector<int> dist(nodes.size()) ; 
                fill(dist.begin(), dist.end(), INF) ; dist[source] = 0 ; 
                vector<int> pred(nodes.size()) ; 
                fill(pred.begin(), pred.end(), -1) ; 
                for(int i=0; i<(int)edges[source].size(); i++)
                {
                    dist[edges[source][i].first] = edges[source][i].second ; 
                    pred[edges[source][i].first] = source  ; 
                }
                set<pair<int,int> > pq ; 
                for(int i=0; i<(int)nodes.size(); i++)
                    pq.insert(make_pair(dist[i],i)) ; 
                while(!pq.empty())
                {
                    pair<int,int> item = *pq.begin() ; 
                    pq.erase(pq.begin()) ; 
                    int v = item.second ; 
                    for(int i=0; i<(int)edges[v].size(); i++)
                    {
                        if(dist[edges[v][i].first] > dist[v] + edges[v][i].second)
                        {
                            pq.erase(std::find(pq.begin(), pq.end(),make_pair(dist[edges[v][i].first],edges[v][i].first))) ; 
                            pq.insert(make_pair(dist[v] + edges[v][i].second,edges[v][i].first)) ; 
                            dist[edges[v][i].first] = dist[v] + edges[v][i].second ; 
                            pred[i] = edges[v][i].first ; 
                        }
                    }
                }
                return make_pair(dist,pred) ; 
            }

pair<vector<int>, vector<int> > shortestwpq(int source) // shortest path djkitra's without priority_queue 
        {
            vector<int> dist(nodes.size()) ; 
            fill(dist.begin(), dist.end(), INF) ; dist[source] = 0 ; 
            vector<int> pred(nodes.size()) ; 
            fill(pred.begin(), pred.end(), -1) ; 
            for(int i=0; i<(int)edges[source].size(); i++)
            {
                dist[edges[source][i].first] = edges[source][i].second ; 
                pred[edges[source][i].first] = source  ; 
            }
            vector<pair<int,int> > pq ; 
            for(int i=0; i<(int)nodes.size(); i++)
                pq.push_back(make_pair(dist[i],i)) ; 
            while(!pq.empty())
            {
                pair<int,int> item = *pq.begin() ; 
                pq.erase(pq.begin()) ; 
                int v = item.second ; 
                for(int i=0; i<(int)edges[v].size(); i++)
                {
                    if(dist[edges[v][i].first] > dist[v] + edges[v][i].second)
                    {
                        dist[edges[v][i].first] = dist[v] + edges[v][i].second ; 
                        pred[i] = edges[v][i].first ; 
                    }
                }
            }
            return make_pair(dist,pred) ; 
        }

正如所料,结果如下: -

优先级为
0
3
2
4

现在使用无优先级队列
0
3
2
6

Answer 2

堆是此任务的最佳选择，因为它保证向队列添加边并删除顶部元素的时间复杂度为 O(log(n))。优先级队列的任何其他实现都会牺牲添加到我们的队列或从队列中删除以获得其他地方的性能提升。根据图的稀疏程度，您可能会使用优先级队列的不同实现来找到更好的性能，但一般来说，最小堆是最好的，因为它平衡了两者。

不是最好的来源，但是： http: //en.wikipedia.org/wiki/Heap_(data_struct)