pythonはディックストラアルゴリズム(アルゴリズム図解練習問題)を実現し、重み図への最短経路を探す

#              
infinity = 10000

#      graph              
graph = dict()
graph['start'] = {}
graph['start']['A'] = 5
graph['start']['B'] = 2
graph['A'] = {}
graph['A']['C'] = 2
graph['A']['D'] = 4
graph['B'] = {}
graph['B']['A'] = 8
graph['B']['C'] = 7
graph['C'] = {}
graph['C']['final'] = 1
graph['D'] = {}
graph['D']['C'] = 6
graph['D']['final'] = 3
graph['final'] = {}

#                        
costs = dict()
costs['A'] = 5
costs['B'] = 2
costs['C'] = infinity
costs['D'] = infinity
costs['final'] = infinity

#                ,         
parents = dict()
parents['start'] = None
parents['A'] = 'start'
parents['B'] = 'start'
parents['C'] = None
parents['D'] = None
parents['final'] = None

#             .
processed = []


#              
def find_lowest_cost_node(costs):
    lowest_cost = 10001
    lowest_cost_node = None
    for node in costs:
        cost = costs[node]
        if cost < lowest_cost and node not in processed:
            lowest_cost = cost
            lowest_cost_node = node
    return lowest_cost_node


#         
while True:
    node = find_lowest_cost_node(costs)
    if node is not None:
        cost = costs[node]
        neighbors = graph[node]
        for n in neighbors.keys():
            new_cost = cost + neighbors[n]
            if new_cost < costs[n]:
                costs[n] = new_cost
                parents[n] = node
                processed.append(node)
    if node == find_lowest_cost_node(costs):
        break

#          
x = 'final'
y = parents[x]
road = ['final']
while y != None :
    road.append(y)
    x = y
    y = parents[x]
print("     :", end='')
for i in range(0, len(road) - 1):
    weizhi = len(road) - i - 1
    print(road[weizhi], end='->')
print("final")
print("        ", costs['final'])