算法——狄克斯特拉算法
狄克斯特拉算法(Dijkstra‘s algorithm)：寻找最快的路径，而不是段数最少的路径。
狄克斯特拉算法用于每条边都有关联数字的图，这些数字叫做权重(weight)。
带权重的图叫加权图(weighted graph)，不带权重的图叫做非加权图(unweighted graph)。
计算非加权图可以使用广度优先搜素，计算加权图可以使用狄克斯特拉算法。
狄克斯特拉算法只适用于有向无环图（directed acyclic graph，DAG）。
如果有负权边，就不能使用狄克斯特拉算法，而要使用贝尔曼-福德算法(Bellman-Ford algorithm)。
步骤：
1）找出最短时间内可以到达的点
2）更新该节点的邻居的开销
3）重复这个过程，直到对图中的所有节点都做了
4）计算最终路径
要点：
广度优先搜索用于在非加权图中查找最短路径
狄克斯特拉算法用于在加权图中查找最短路径
仅当权重为正时狄克斯特拉算法才管用
如果图中包含负权边，请使用贝尔曼-福德算法
# dijkstra 狄克斯特拉算法 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 if __name__ == ‘__main__‘: 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‘] = {} infinity = float(‘inf‘) costs = {} costs[‘a‘] = 6 costs[‘b‘] = 2 costs[‘fin‘] = infinity parents = {} parents[‘a‘] = ‘start‘ parents[‘b‘] = ‘start‘ parents[‘fin‘] = None processed = [] node = find_lowest_cost_node(costs) # 在未处理的节点中找出开销最小的节点 while node is not None: # 这个while循环在所有节点都被处理过后结束 print(node) 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)
原文：https://www.cnblogs.com/noonjuan/p/10923973.html