我尝试在循环加权图上使用 Djikstra 算法而不使用优先级队列（堆）并且它有效。
Wikipedia 指出该算法的原始实现不使用优先级队列并且在 O(V 2 ) 时间内运行。
现在如果我们只是移除优先级队列并使用普通队列，运行时间是线性的，即 O(V+E)。
有人可以解释为什么我们需要优先队列吗？
问问题
17794 次
4 回答
11
我有完全相同的疑问，并发现了一个测试用例，其中没有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。
此时，使用 path 将 dist b/w 0 和 3 计算为 6 0->1->3，并将 1 标记为已访问。
现在节点 2 已被访问，并且 dist b/w 0 和 1 使用 path 更新为值 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) ;
}
正如预期的那样，结果如下：-
使用priority_queue
0
3
2
4
现在使用没有优先级队列
0
3
2
6
于 2015-01-24T04:17:51.697 回答
3
Like Moataz Elmasry said the best you can expect is O(|E| + |V|.|logV|) with a fib queue. At least when it comes to big oh values.
The idea behind it is, for every vertex(node) you are currently working on, you already found the shortest path to. If the vertex isn't the smallest one, (distance + edge weight) that isn't necessarily true. This is what allows you to stop the algorithm as soon as you have expanded(?) every vertex that is reachable from your initial vertex. If you aren't expanding the smallest vertex, you aren't guaranteed to be finding the shortest path, thus you would have to test every single path, not just one. So instead of having to go through every edge in just one path, you go through every edge in every path.
Your estimate for O(E + V) is probably correct, the path and cost you determined on the other hand, are incorrect. If I'm not mistaken the path would only be the shortest if by any chance the first edge you travel from every vertex just happens to be the smallest one.
So Dijkstra's shortest path algorithm without a queue with priority is just Dijkstra's path algorithm ;)
于 2013-05-16T14:40:49.557 回答
2
对于稀疏图，如果使用二进制最小堆运行时是（E*logV），但是如果使用斐波那契堆实现，运行时将是（VlogV+E）。
于 2012-12-13T01:31:51.837 回答
0
堆是此任务的最佳选择，因为它保证 O(log(n)) 可以将边添加到我们的队列并删除顶部元素。优先级队列的任何其他实现都会牺牲添加到我们的队列或从中删除以在其他地方获得性能提升。根据图的稀疏程度，您可能会使用不同的优先级队列实现找到更好的性能，但一般来说，最小堆是最好的，因为它可以平衡两者。
不是最好的来源，但：http://en.wikipedia.org/wiki/Heap_(data_structure)
于 2012-11-18T03:05:30.433 回答