Skip to content

Instantly share code, notes, and snippets.

# panyam/dijkstra_shortest_path.py

Last active February 21, 2017 17:59
Show Gist options
• Save panyam/f6a6612b5ca5f773837891acc0b24410 to your computer and use it in GitHub Desktop.
Dijkstra's shortest path algorithm - basic version
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 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
to join this conversation on GitHub. Already have an account? Sign in to comment