Getting wrong results with implementation of Dijkstra's algorithm using PriorityQueue

Question

I have implemented Dijkstra's algorithm using the PriorityQueue class of the queue module in Python.

But I am not always getting the correct result according to the online judge. Something must be missing in the below-given code, but I have no idea what.

What is wrong with my code?

from queue import PriorityQueue

class Solution:
    #Function to find the shortest distance of all the vertices
    #from the source vertex S.
    def dijkstra(self, V, adj, S):
        #code here
        q=PriorityQueue()
        distance=[-1]*V
        distance[S]=0
        visited=set()
        visited.add(S)
        for i in adj[S]:
            distance[i[0]]=distance[S]+i[1]
            q.put([i[1],i[0]])
        while not q.empty():
            w,s=q.get()
            visited.add(s)
            for i in adj[s]:
                d=distance[s]+i[1]
                if distance[i[0]]==-1:
                    distance[i[0]]=d
                elif distance[i[0]]>d:
                    distance[i[0]]=d
                if i[0] not in visited:
                    q.put([i[1],i[0]])
        return distance
            

#{ 
#  Driver Code Starts
#Initial Template for Python 3

import atexit
import io
import sys
    
if __name__ == '__main__':
    test_cases = int(input())
    for cases in range(test_cases):
        V,E = map(int,input().strip().split())
        adj = [[] for i in range(V)]
        for i in range(E):
            u,v,w = map(int,input().strip().split())
            adj[u].append([v,w])
            adj[v].append([u,w])
        S=int(input())
        ob = Solution()
        
        res = ob.dijkstra(V,adj,S)
        for i in res:
            print(i,end=" ")
        print()

# } Driver Code Ends

Sample Input for one test case:

9 14
0 1 4
0 7 8 
1 7 11
1 2 8
7 6 1
7 8 7
2 8 2    
8 6 6
2 5 4
2 3 7
6 5 2
3 5 14 
3 4 9
5 4 10
0

Expected Output:

0 4 12 19 21 11 9 8 14

Problem:

My code returns this instead:

0 4 12 19 26 16 18 8 14

Answer 1

The problem is that you are giving priority to the edges with the least weight, but you should give priority to paths with the least weight.

So near the end of your code change:

q.put([i[1],i[0]])

to:

q.put([d,i[0]])

This will solve it.

However, some comments:

If you use a priority queue it should not be necessary to compare a previously stored distance for a node with a new distance, as the priority queue's role is to make sure you visit a node via the shortest path upon its first visit. With a bit of code reorganisation, you can get rid of that minimal-distance test.

Once you have that in place, you also do not need to have visited, as it is enough to check that the node's distance is still at -1 (assuming weights are never negative). When that is the case, it means you haven't visited it yet.

It is also a bit more efficient if you store tuples on the queue instead of lists.

And you can reorganise the code so that you only need to push the initial cell to the queue before starting the traversal loop.

Finally, instead of one letter variables, it is more readable if you use descriptive names, like node and weight:

class Solution:
    def dijkstra(self, V, adj, S):
        queue = PriorityQueue()
        distances = [-1] * V
        queue.put((0, S))
        while not queue.empty():
            dist, node = queue.get()
            if distances[node] == -1:
                distances[node] = dist
                for neighbor, weight in adj[node]:
                    queue.put((dist + weight, neighbor))
        return distances