Dijkstra algorithm not working even though passes the sample test cases

Question

So I have followed Wikipedia's pseudocode for Dijkstra's algorithm as well as Brilliants. https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm#Pseudocode https://brilliant.org/wiki/dijkstras-short-path-finder/. Here is my code which doesn't work. Can anyone point in the flaw in my code?

# Uses python3

from queue import Queue

n, m = map(int, input().split())
adj = [[] for i in range(n)]

for i in range(m):
    u, v, w = map(int, input().split())
    adj[u-1].append([v, w])
    adj[v-1].append([u, w])

x, y = map(int, input().split())
x, y = x-1, y-1
q = [i for i in range(n, 0, -1)]
#visited = set()
# visited.add(x+1)
dist = [float('inf') for i in range(len(adj))]
dist[x] = 0
# print(adj[visiting])
while len(q) != 0:

    visiting = q.pop()-1
    for i in adj[visiting]:
        u, v = i
        dist[u-1] = dist[visiting]+v if dist[visiting] + \
            v < dist[u-1] else dist[u-1]
# print(dist)
if dist[y] != float('inf'):
    print(dist[y])
else:
    print(-1)

trincot · Accepted Answer · 2020-06-27 17:32:39Z

Your algorithm is not implementing Dijkstra's algorithm correctly. You are just iterating over all nodes in their input order and updating the distance to the neighbors based on the node's current distance. But that latter distance is not guaranteed to be the shortest distance, because you iterate some nodes before their "turn". Dijkstra's algorithm specifies a particular order of processing nodes, which is not necessarily the input order.

The main ingredient that is missing from your algorithm, is a priority queue. You did import from Queue, but never use it. Also, it lacks the marking of nodes as visited, a concept which you seemed to have implemented a bit, but which you commented out.

The outline of the algorithm on Wikipedia explains the use of this priority queue in the last step of each iteration:

Otherwise, select the unvisited node that is marked with the smallest tentative distance, set it as the new "current node", and go back to step 3.

There is currently no mechanism in your code that selects the visited node with smallest distance. Instead it picks the next node based on the order in the input.

To correct your code, please consult the pseudo code that is available on that same Wikipedia page, and I would advise to go for the variant with priority queue.

In Python you can use heapq for performing the actions on the priority queue (heappush, heappop).

VickySekhon · Accepted Answer · 2024-07-21 21:28:11Z

0

Good question. You must use a priority queue to track visited nodes that sorts those nodes/paths based on their length (shortest first).

answered Jul 21, 2024 at 21:28

VickySekhon

215 bronze badges

1 Comment

L Tyrone Over a year ago

Any chance you could add the code for implementing this solution? It will make your answer more useful to others who may land here in the future. Thanks.

Collectives™ on Stack Overflow

Dijkstra algorithm not working even though passes the sample test cases

2 Answers 2

Comments

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related