Question Need help with a problem in the implementation of Dijkstra's algorithm.

[quentisa]

I'm presently working on implementing Dijkstra's method for a graph traversal problem, however I'm having trouble figuring out an error. The method succeeds, but the shortest path it generates is inaccurate.
Here's a piece of code that computes the shortest distances:

distances = [float('inf')] * num_nodes
distances[source] = 0
visited = [False] * num_nodes

while True:
    min_distance = float('inf')
    min_node = -1

    for node in range(num_nodes):
        if not visited[node] and distances[node] < min_distance:
            min_distance = distances[node]
            min_node = node

    if min_node == -1:
        break

    visited[min_node] = True

    for neighbor in graph[min_node]:
        new_distance = distances[min_node] + graph[min_node][neighbor]
        if new_distance < distances[neighbor]:
            distances[neighbor] = new_distance

I went through the code and double-checked my graph representation to ensure that the edge weights are not negative, and I read the scaler article for Dijkstra's algorithm to get a check. Despite the fact that the method ends, the distances calculated are incorrect for some nodes.

I believe there is a problem with the termination condition or the way I label nodes as visited. Could the loop condition or the method I update the visited list have a logical flaw? I can't figure out what's causing the wrong distances.

I would highly appreciate your aid if you have any thoughts or recommendations on how to address this mistake and assure the right shortest path lengths. Thank you ahead of time!"

 

[simmerskool]

wondering if you've tried openai chatgpt since I've heard that it is good at checking code