Dijkstra implementation keeps giving wrong shortest paths. #14214
-
|
My Dijkstra implementation keeps giving wrong shortest paths. Getting infinite loops or incorrect distances. |
Beta Was this translation helpful? Give feedback.
Replies: 3 comments
-
|
Here's a production-ready Dijkstra's algorithm with priority queue: import heapq
from collections import defaultdict
def dijkstra(graph, start):
# Priority queue: (distance, node)
pq = [(0, start)]
distances = {node: float('inf') for node in graph}
distances[start] = 0
prev_node = {}
while pq:
current_dist, current = heapq.heappop(pq)
if current_dist > distances[current]:
continue
for neighbor, weight in graph[current].items():
distance = current_dist + weight
if distance < distances[neighbor]:
distances[neighbor] = distance
prev_node[neighbor] = current
heapq.heappush(pq, (distance, neighbor))
return distances, prev_node
# Example usage
graph = {
'A': {'B': 4, 'C': 2},
'B': {'A': 4, 'C': 1, 'D': 5},
'C': {'A': 2, 'B': 1, 'D': 8},
'D': {'B': 5, 'C': 8}
}
distances, prev = dijkstra(graph, 'A')
print(distances) # {'A': 0, 'B': 2, 'C': 2, 'D': 7} |
Beta Was this translation helpful? Give feedback.
-
|
@PanthersHowl If your Dijkstra’s algorithm is failing, it is likely due to one of these three logic errors:
Correct Python Implementation (using import heapq
def dijkstra(graph, start):
# distances[node] = infinity by default
distances = {node: float('infinity') for node in graph}
distances[start] = 0
# Priority Queue stores (distance, node)
pq = [(0, start)]
while pq:
current_dist, current_node = heapq.heappop(pq)
# 1. Skip if we found a better path already
if current_dist > distances[current_node]:
continue
for neighbor, weight in graph[current_node].items():
distance = current_dist + weight
# 2. Relaxation Step
if distance < distances[neighbor]:
distances[neighbor] = distance
heapq.heappush(pq, (distance, neighbor))
return distancesQuick Checklist:
|
Beta Was this translation helpful? Give feedback.
-
|
@PanthersHowl If this solution helped you, please mark it as an approved answer to help others. |
Beta Was this translation helpful? Give feedback.
Here's a production-ready Dijkstra's algorithm with priority queue: