狄克斯特拉算法

狄克斯特拉算法，当然是狄克斯特拉发明的。

这是相对广度优先搜索而产生的在加权路图中寻找最短路径的算法。

加权图，就是在图的每一条路径上都标明这条路的权重。

用汽车和道路来简单说明的话，广度优先搜索是找到起点到终点的最短路程，但是其中并不会考虑交通状况，塞车问题。而狄克斯特拉算法，则用权重来表示时间，权重越大，越塞车。所以狄克斯特拉算法是找出最短时间（权重）到达终点的路径。

算法的实现。

1）构造出三个表格

第一个表格

````

graph = {}

graph['start'] = {}

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

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

#print(graph['start']['a'])

graph['a'] = {}

graph['a']['fin'] = 1

graph['b'] = {}

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

graph['b']['fin'] = 5

graph['fin'] = {}

#print(graph)

infinity = float('inf')

第二个表格，表达到达目的的权重

costs = {}

#到达a的权重是 6

costs['a'] = 6

#到达b的权重是2

costs['b'] = 2

costs['fin'] = infinity

#第三个表格，则是在找父节点

parents = {}

parents['a'] = 'start'

parents['b'] = 'start'

parents['fin'] = None

processed = []

````