Why does Dijkstra's Algorithm use a heap (priority queue)?

Question

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

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

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?

Answer 1

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

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) ; 

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.

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 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.

So, your algorithm fails without using the priority_queue.

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) ; 
            }

As expected the results were as follows :-

With priority_queue
0
3
2
4

Now using without priority queue
0
3
2
6

Answer 2

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 ;)