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

Question

我试过在循环加权图上使用Djikstra的算法而不使用优先级队列（堆），并且它起作用了。

维基百科指出，此算法的原始实现不使用优先级队列，而是在O（V2）时间运行。

现在，如果我们只是删除优先级队列并使用普通队列，则运行时间是线性的，即O（V + E）。

有人可以解释为什么我们需要优先级队列吗？

Answer 1

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

假设我有一个Graph对象g，方法addEdge(a,b,w)将权重a的边从顶点b添加到顶点w。

现在，让我定义下图：

   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。

在这个时间点，使用路径 0->1->3将dist b / w 0和3计算为6，并将1标记为已访问。

现在访问了节点2，并且使用路径 0->2->1将dist b / w 0和1更新为值3，但是由于节点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) ; 
        }

如预期的那样，结果如下：

使用priority_queue
0
3
2
4

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