simple Python implementation of Dijkstra's Algorithm

python-dijkstras.py

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}