# the graph graph graph start graph start graph start graph graph fin gr

 ``` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67``` ```# the graph graph = {} graph['start'] = {} graph['start']['a'] = 6 graph['start']['b'] = 2 graph['a'] = {} graph['a']['fin'] = 1 graph['b'] = {} graph['b']['a'] = 3 graph['b']['fin'] = 5 graph['fin'] = {} # the cost table infinity = float('inf') costs = {} costs['a'] = 6 costs['b'] = 2 costs['fin'] = infinity # the parents table parents = {} parents['a'] = 'start' parents['b'] = 'start' parents['fin'] = None processed = [] def find_lowest_cost_node(costs): # find the lowest unprocessed cost node lowest_cost = float('inf') lowest_cost_node = None # Go through each node. for node in costs: cost = costs[node] # if it's lowest cost so far and hasn't been processed yet... if cost < lowest_cost and node not in processed: # ... set ut as the new lowest-cost node. lowest_cost = cost lowest_cost_node = node return lowest_cost_node # find the lowest-cost node that you haven't processed yet. node = find_lowest_cost_node(costs) # if you've processed all the nodes, this while loop is done. while node is not None: cost = costs[node] # go through all the neighbors of this node neighbors = graph[node] for n in neighbors.keys(): new_cost = cost + neighbors[n] # if it's cheaper to get to this neighbor by going through this node... if costs[n] > new_cost: # ...update the cost for this node. costs[n] = new_cost # this node becomes the new parent for this neighbor. parents[n] = node # mark the node as processed processed.append(node) # find the next node to process, and loop. node = find_lowest_cost_node(costs) print('Costs from the start to each node: ') print(costs) ```