为什么Dijkstra的算法使用堆（优先级队列）？ [英] Why does Dijkstra's Algorithm use a heap (priority queue)?

问题描述

我曾尝试在不使用优先级队列（堆）的情况下在循环加权图上使用Djikstra的算法，并且该算法有效。

I have tried using Djikstra's Algorithm on a cyclic weighted graph without using a priority queue (heap) and it worked.

维基百科指出，该算法的原始实现不使用优先级队列，并且运行时间为O（V ² ）。

Wikipedia states that the original implementation of this algorithm does not use a priority queue and runs in O(V²) time.

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

Now if we just removed the priority queue and used normal queue, the run time is linear, i.e. O(V+E).

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

Can someone explain why we need the priority queue?

推荐答案

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

I had the exact same doubt and found a test case where the algorithm without a priority_queue would not work.

假设我有一个Graph对象 g ，方法 addEdge（a，b，w），可将顶点 a 中的边添加到顶点 b 重量 w 。

Let's say I have a Graph object g, a method addEdge(a,b,w) which adds edge from vertex a to vertex b with weight w.

现在，让我定义下图：

Now, let me define the following graph :-

   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。

Now, say our queue contains the nodes in the following order {0,1,2,3 } So, node 0 is visited first then node 1 is visited.

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

At this point of time the dist b/w 0 and 3 is computed as 6 using the path 0->1->3, and 1 is marked as visited.

Now节点使用路径 0-> 2-> 1 来访问2并将dist b / w 0和1更新为值3，但是由于节点1被标记为已访问，则无法更改距离b / w 0和3（使用最佳路径）（`0-> 2-> 1-> 3）为4。

Now node 2 is visited and dist b/w 0 and 1 is updated to the value 3 using the path 0->2->1, but since node 1 is marked visited, you cannot change the distance b/w 0 and 3 which (using the optimal path) (`0->2->1->3) is 4.

，则您的算法会在不使用priority_queue的情况下失败。

So, your algorithm fails without using the priority_queue.

它报告dist b / w 0和3为6，而实际上应为4。

It reports dist b/w 0 and 3 to be 6 while in reality it should be 4.

现在，这是我用于实现算法的代码：-

Now, here is the code which I used for implementing the algorithm :-

            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

With priority_queue
0
3
2
4

现在使用没有优先级的队列

0

3

2

6

Now using without priority queue
0
3
2
6

这篇关于为什么Dijkstra的算法使用堆（优先级队列）？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！