Create a gist now

Instantly share code, notes, and snippets.

What would you like to do?
Dijkstra's shortest path algorithm - basic version
def shortest_path(source, target):
"""
Return the shortest path from the source to target.
"""
# Keeps track of the parent node for a node in the path between source and target.
parents = defaultdict(lambda: None)
# Keep track of the distance of each node to the source node
distances = {source: 0, target: INFINITY}
# The nodes that are known to have the shortest path in each iteration
known_nodes = {source}
# A heap of nodes is used where they nodes are sorted by their distance to the source node
nodeheap = PQ([source, target],
comparator = lambda x,y: distances[x] - distances[y])
# Add all the neighbours of the starting source node to the heap
for neighbour in neighbours_of(source):
distances[neighbour] = source.distance_to(neighbour)
nodeheap.push(neighbour)
last = None
while last != target and nodeheap:
# get the node that is closest to the source at this point
# This should be the pop operation of the priority queue
currnode = nodeheap.pop()
# If the node is already known then skip its children
if currnode in known_nodes: continue
# Go through each of the curr node's neighbours
# and update it's distances. It's "new" distance can either
# be "via" its parent (currnode) or directly from the
# source node if such an edge exists.
for child in neighbours_of(currnode):
curr_dist = distances[currnode] + currnode.distance_to(child)
if child not in distances or curr_dist < distances[child]:
distances[child] = curr_dist
parents[child] = currnode
last = currnode
known.add(currnode)
# Return the list of all parent nodes that can be walked up
# backwards to extract the path to the source (in reverse)
# The to the target node is simply distances[target]
return distances, parents
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment