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