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

编程入门行业动态更新时间:2024-10-19 07:27:28

本文介绍了为什么Dijkstra的算法使用堆（优先级队列）？的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！问题描述

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

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

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

Wikipedia states that the original implementation of this algorithm does not use a priority queue and runs in O(V2) 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