Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
simple Python implementation of Dijkstra's Algorithm
from collections import defaultdict
import math
class DirectedGraph(dict):
"""Create a directed Graph. Root keys contain a dictionary of other nodes they are directed to with
corresponding weight"""
def __missing__(self, key):
value = self[key] = {key: 0} # A keys distance to itself is always 0
return value
def connect(self, node1, node2, weight):
nodes = self.keys()
if node1 not in nodes:
self[node1]
if node2 not in nodes:
self[node2]
self[node1][node2] = weight
def connected_nodes(self, node):
return {k: v for k, v in self[node].items() if k != node}
def dijkstras(self, start, end):
def get_next():
remaining = {k: v for k, v in distance.items() if k not in finished}
next_node = min(remaining, key=remaining.get)
return next_node
def step(node):
cost = 0 if parent[node] is None else distance[node] # If no parents, then this is the starting node
for n, w in self.connected_nodes(node).items():
if distance[n] is None or distance[n] > w + cost:
parent[n] = node
distance[n] = cost + w
finished.append(node)
def print_path():
path = [end]
node = end
while parent[node] != start:
path.append(parent[node])
node = parent[node]
path.append(start)
path.reverse()
print("The shortest path from A to D is: ")
print(" --> ".join(path))
finished = []
distance = {}
parent = {}
for node in self.keys():
distance[node] = 0 if (node == start) else math.inf
parent[node] = None
step(start)
while end not in finished:
nextNode = get_next()
step(nextNode)
print_path()
print("finished: ", finished)
print("Parent: ", parent)
return distance
g = DirectedGraph()
g.connect('A', 'B', 5)
g.connect('A', 'F', 10)
g.connect('B', 'F', 4)
g.connect('B', 'C', 1)
g.connect('F', 'B', 3)
# g.connect('F', 'B', -9) # dijkstras can not accommodate this
g.connect('F', 'C', 7)
g.connect('C', 'E', 2)
g.connect('C', 'D', 6)
g.connect('E', 'D', 3)
g.connect('E', 'F', 1)
g.dijkstras('A', 'D')
### output ###
#The shortest path from A to D is:
#A --> B --> C --> E --> D
#finished: ['A', 'B', 'C', 'E', 'F', 'D']
#Parent: {'A': None, 'B': 'A', 'F': 'B', 'C': 'B', 'E': 'C', 'D': 'E'}
#Out[1]:
#{'A': 0, 'B': 5, 'C': 6, 'D': 11, 'E': 8, 'F': 9}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.