Skip to content

Instantly share code, notes, and snippets.

What would you like to do?
Python implementation of Dijkstra's Algorithm using heapq
import heapq
from collections import defaultdict
class Graph:
def __init__(self, n):
self.nodes = set(range(n))
self.edges = defaultdict(list)
self.distances = {}
def add_edge(self, from_node, to_node, distance):
self.distances[from_node, to_node] = distance
def dijkstra(graph, initial):
visited = {initial: 0}
h = [(0, initial)]
path = {}
nodes = set(graph.nodes)
while nodes and h:
current_weight, min_node = heapq.heappop(h)
while min_node not in nodes:
current_weight, min_node = heapq.heappop(h)
except IndexError:
for v in graph.edges[min_node]:
weight = current_weight + graph.distances[min_node, v]
if v not in visited or weight < visited[v]:
visited[v] = weight
heapq.heappush(h, (weight, v))
path[v] = min_node
return visited, path
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment