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

Question

我曾尝试在循环加权图上使用Djikstra的算法，而不使用优先级队列（堆），结果成功了。

Wikipedia指出，该算法的原始实现不使用优先级队列，而是在O（V²）时间内运行。

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

有人能解释一下为什么我们需要优先队列吗？

Answer 1

对于稀疏图，如果使用二进制最小堆实现运行时为（E*logV），但是如果使用斐波那契堆实现它，运行时将为（VlogV E）。

Answer 2

就像Moataz Elmasry所说，您可以期望的最好结果是带有fib队列的O（|E||V|.|logV|）。至少在大oh值方面是这样。

其背后的思想是，对于您当前正在处理的每个顶点（节点），您已经找到了到的最短路径。如果该顶点不是最小的（距离边权重），则不一定是真的。这允许您在展开（？）后立即停止算法从初始顶点可到达的每个顶点。如果不扩展最小顶点，则不能保证找到最短路径，因此必须测试每条路径，而不仅仅是一条。因此，你不必只通过一条路径中的每条边，而是通过每条路径中的每一条边。

您对O（E V）的估计可能是正确的，另一方面，您确定的路径和成本不正确。如果我没有记错的话，路径只会是最短的，如果你从每个顶点行进的第一条边恰好是最小的一条。

因此，没有优先级队列的Dijkstra最短路径算法就是Dijksstra的路径算法；）

Answer 3

我有完全相同的疑问，并发现了一个测试用例，其中没有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) ; 

现在，假设我们的队列包含以下顺序的节点< code>{0，1，2，3 }因此，首先访问节点0，然后访问节点1。

此时，使用路径＜代码＞0将距离b/w 0和3计算为6-

现在访问节点2并使用路径0-将dist b/w 0和1更新为值3

因此，您的算法在不使用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