👀 Views: 240 💬 Answers: 1 📅 Created: 2025-06-05

algorithm dijkstra graph Python

I'm maintaining legacy code that I'm having trouble with I'm relatively new to this, so bear with me. I'm implementing Dijkstra's algorithm in Python to find the shortest path in a weighted graph, but I've encountered an scenario where the algorithm returns incorrect results for certain sparse graphs. My implementation uses a priority queue, but it seems to unexpected result when the graph has disconnected components or when the weights are very large. Here’s how I set it up: ```python import heapq class Graph: def __init__(self): self.graph = {} def add_edge(self, u, v, weight): if u not in self.graph: self.graph[u] = [] self.graph[u].append((v, weight)) def dijkstra(self, start): distances = {node: float('inf') for node in self.graph} distances[start] = 0 priority_queue = [(0, start)] while priority_queue: current_distance, current_node = heapq.heappop(priority_queue) for neighbor, weight in self.graph.get(current_node, []): distance = current_distance + weight if distance < distances[neighbor]: distances[neighbor] = distance heapq.heappush(priority_queue, (distance, neighbor)) return distances ``` I’ve tried running it with the following graph: ```python g = Graph() g.add_edge('A', 'B', 1) g.add_edge('B', 'C', 2) g.add_edge('A', 'D', 5) g.add_edge('D', 'E', 1) ``` When I call `g.dijkstra('A')`, I expect the shortest distance to node 'C' to be 3, but it returns 5. Also, if I add an edge from 'C' to 'E' with a weight of 1: ```python g.add_edge('C', 'E', 1) ``` I expect the distance to 'E' from 'A' to be 4, but it still shows 5. Is there something I'm missing in handling disconnected nodes or how I update the distances? Any insights would be appreciated! Am I missing something obvious? The stack includes Python and several other technologies. For reference, this is a production service. Hoping someone can shed some light on this. Any ideas what could be causing this?