# 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)