Skip to content

Instantly share code, notes, and snippets.

@sutyrin
Forked from econchick/gist:4666413
Last active August 29, 2015 14:13
Show Gist options
  • Save sutyrin/4311bacedbb6727b5202 to your computer and use it in GitHub Desktop.
Save sutyrin/4311bacedbb6727b5202 to your computer and use it in GitHub Desktop.
class Graph:
def __init__(self):
self.nodes = set()
self.edges = defaultdict(list)
self.distances = {}
def add_node(self, value):
self.nodes.add(value)
def add_edge(self, from_node, to_node, distance):
self.edges[from_node].append(to_node)
self.edges[to_node].append(from_node)
self.distances[(from_node, to_node)] = distance
def dijsktra(graph, initial):
visited = {initial: 0}
path = {}
nodes = set(graph.nodes)
while nodes:
min_node = None
for node in nodes:
if node in visited:
if min_node is None:
min_node = node
elif visited[node] < visited[min_node]:
min_node = node
if min_node is None:
break
nodes.remove(min_node)
current_weight = visited[min_node]
for edge in graph.edges[min_node]:
weight = current_weight + graph.distance[(min_node, edge)]
if edge not in visited or weight < visited[edge]:
visited[edge] = weight
path[edge] = min_node
return visited, path
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment