總結《算法圖解》第7章

狄克斯特拉算法

主要思想是：

1、找出最便宜的節點，在最短時間内前往的節點，建立一個costs圖和parents圖，也就是出發點到各點的距離和父子節點關系圖。

2、根據第一步找得到的節點，找到其鄰居節點，更新經過第一步找到點的costs圖和已該節點為父節點的parents圖。

3、重複以上兩個過程，直到圖中所有點都已經做過了以上循環。

4、計算最終路徑。

# 狄克斯特拉算法适用于有向無環圖，不包含負權邊
# 用散清單（Python 裡面的字典）描述該圖
graph = {}
graph['s'] = {}
graph['s']['a'] = 6
graph['s']['b'] = 2
graph['a'] = {}
graph['a']['d'] = 1
graph['b'] = {}
graph['b']['a'] = 3
graph['b']['d'] = 5
graph['d'] = {}

# 用散清單描述花銷
infinity = float('+inf')
costs = {}
costs['a'] = 6
costs['b'] = 2
costs['d'] = infinity

# 用散清單來描述父節點
parents = {}
parents['a'] = 's'
parents['b'] = 's'
parents['d'] = None

processed = []

# 找到花銷裡面最小的節點
def lowest_cost(costs):
    smallest = float('inf')
    lowest_node = None
    for node in costs:  # 在python字典裡面，node就代表了key，用cost[key]就可以表達key對應的value
        cost = costs[node]
        if cost < smallest and node not in processed:
            smallest = cost
            lowest_node = node
    return lowest_node

# 更新花銷節點和父節點

name = lowest_cost(costs)
print(name)
while name is not None:  # 字典裡面的key不是空，代表還有節點
    for n in graph[name].keys():
        new_costs = costs[name] + graph[name][n]# 通過cost['b'] = 2，加上graph['b']['a'] = 3 ,graph['b']['d'] = 5就可以得到新的cost表
        if new_costs < costs[n]:
            costs[n] = new_costs
            parents[n] = name
    processed.append(name)
    name = lowest_cost(costs)
    print(costs)