'''

迪克斯特拉算法：

1、以字典的方式更新图，包括权重

2、创建开销字典，关键在于起点临近的点开销为实际数值，其他点为暂时未到达，开销为无穷，随后更新

3、创建父节点列表保存每个点的父节点，以便记录走过的路径

'''

from queue import LifoQueue

graph = {}

graph['start'] = {}

graph['start']['a'] = 6

graph['start']['b'] = 2

graph['a'] = {}

graph['a']['end'] = 4

graph['b'] = {}

graph['b']['a'] = 3

graph['b']['c'] = 2

graph['c'] = {}

graph['c']['end'] = 3

graph['end'] = {}

print(graph)

infinity = float('inf')

costs = {}

costs['a'] = 6

costs['b'] = 2

costs['c'] = infinity

costs['end'] = infinity

parents = {}

parents['a'] = 'start'

parents['b'] = 'start'

parents['c'] = 'b'

parents['end'] = None

processed = []

def find_lowest_cost_node(costs):

    lowest_cost = float('inf')

    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

node = find_lowest_cost_node(costs)

while(node is not None):

    cost = costs[node]

    neighbors = graph[node]

    for n in neighbors.keys():

        new_cost = cost + neighbors[n]

        if costs[n] > new_cost:

            costs[n] = new_cost

            parents[n] = node

    processed.append(node)

    node = find_lowest_cost_node(costs)

#输出最短路径

p = 'end'

path = LifoQueue()

while(True):

    path.put(p)

    if(p == 'start'):

        break

    p = parents[p]

while not path.empty():

    print(path.get())