Dijkstra’s algorithm

狄克斯特拉算法包含4个步骤
(1) 找出最便宜的节点，即可在最短时间内前往的节点。
(2) 对于该节点的邻居，检查是否有前往它们的更短路径，如果有，就更新其开销。
(3) 重复这个过程，直到对图中的每个节点都这样做了。
(4) 计算最终路径。

只适用于有向无环图

关键理念：找出图中最便宜的节点，并确保没有到该节点的更便宜的路径!
不能处理负权边 

  1. #节点之间的邻居关系，单向的
  2. graph = {}
  3. graph["start"] = {}
  4. graph["start"]["a"] = 6
  5. graph["start"]["b"] = 2
  6. graph["a"] = {}
  7. graph["a"]["finish"] = 1
  8. graph["b"] = {}
  9. graph["b"]["a"] = 3
  10. graph["b"]["finish"] = 5
  11. #节点的消耗
  12. infinity = float("inf")
  13. costs = {}
  14. costs["a"] = 6
  15. costs["b"] = 2
  16. costs["finish"] = infinity
  17. #保存父节点，路径图
  18. parents = {}
  19. parents["a"] = "start"
  20. parents["b"] = "start"
  21. parents["finish"] = None
  22. processed = []
  23. def find_lowest_cost_node(costs):
  24.     lowest_cost = float("inf")
  25.     lowest_cost_node = None
  26.     for node in costs:
  27.         if costs[node] < lowest_cost and node not in processed:
  28.             lowest_cost = costs[node]
  29.             lowest_cost_node = node
  30.     return lowest_cost_node
  31. def find_path():
  32.     node = find_lowest_cost_node(costs)
  33.     while node is not None:
  34.         cost = costs[node]
  35.         if node not in graph:
  36.             processed.append(node)
  37.             node = find_lowest_cost_node(costs)
  38.             continue
  39.         neightbors = graph[node]
  40.         for n in neightbors.keys():
  41.             new_cost = cost + neightbors[n]
  42.             if new_cost < costs[n]:
  43.                 costs[n] = new_cost
  44.                 parents[n] = node
  45.         processed.append(node)
  46.         node = find_lowest_cost_node(costs)
  47. find_path()
  48. print(parents)