Reply to thread

Message

<blockquote data-quote="quentisa" data-source="post: 1049594" data-attributes="member: 98424">I&#039;m presently working on implementing Dijkstra&#039;s method for a graph traversal problem, however I&#039;m having trouble figuring out an error. The method succeeds, but the shortest path it generates is inaccurate.Here&#039;s a piece of code that computes the shortest distances:[CODE]distances = [float(&#039;inf&#039;)] * num_nodesdistances[source] = 0visited = [False] * num_nodeswhile True:&nbsp; &nbsp; min_distance = float(&#039;inf&#039;)&nbsp; &nbsp; min_node = -1&nbsp; &nbsp; for node in range(num_nodes):&nbsp; &nbsp; &nbsp; &nbsp; if not visited[node] and distances[node] &lt; min_distance:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; min_distance = distances[node]&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; min_node = node&nbsp; &nbsp; if min_node == -1:&nbsp; &nbsp; &nbsp; &nbsp; break&nbsp; &nbsp; visited[min_node] = True&nbsp; &nbsp; for neighbor in graph[min_node]:&nbsp; &nbsp; &nbsp; &nbsp; new_distance = distances[min_node] + graph[min_node][neighbor]&nbsp; &nbsp; &nbsp; &nbsp; if new_distance &lt; distances[neighbor]:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; distances[neighbor] = new_distance[/CODE]I went through the code and double-checked my graph representation to ensure that the edge weights are not negative, and I read the <a href="https://www.scaler.com/topics/data-structures/dijkstra-algorithm/" target="_blank">scaler</a> article for Dijkstra&#039;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&#039;t figure out what&#039;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!&quot;</blockquote>

[QUOTE="quentisa, post: 1049594, member: 98424"] 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: [CODE]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[/CODE] I went through the code and double-checked my graph representation to ensure that the edge weights are not negative, and I read the [URL='https://www.scaler.com/topics/data-structures/dijkstra-algorithm/']scaler[/URL] 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!" [/QUOTE]

Verification