使用狄克斯特拉算法找出下圖中從起點(diǎn)至終點(diǎn)耗時(shí)最短的路徑，路徑上的每個(gè)數(shù)字表示的都是時(shí)間，單位分鐘。

狄克斯特拉算法包含的4個(gè)步驟：

（1）找出開銷/消耗“最便宜”的節(jié)點(diǎn)，即在最短時(shí)間內(nèi)到達(dá)的節(jié)點(diǎn)

（2）對(duì)于該節(jié)點(diǎn)的鄰居，檢查是否有前往它們的更短路徑，如果有，更新該節(jié)點(diǎn)的鄰居的開銷

（3）重復(fù)上述過程，直到對(duì)圖中的每個(gè)節(jié)點(diǎn)都這樣做了

（4）計(jì)算最終路徑

?

python代碼實(shí)現(xiàn)：

            
              # 描述各節(jié)點(diǎn)、時(shí)間開銷、父節(jié)點(diǎn)信息
# 創(chuàng)建節(jié)點(diǎn)信息，start起點(diǎn)，fin終點(diǎn)
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"]={}

# 創(chuàng)建開銷/時(shí)間表
infinity = float("inf") #無窮大
costs={}
costs["a"]=6
costs["b"]=2
costs["fin"]=infinity   #暫時(shí)將通往終點(diǎn)的時(shí)間，定義為無窮大

# 路徑中父節(jié)點(diǎn)信息
parents= {}
parents["a"]="start"
parents["b"]="start"
parents["fin"]=None

# 記錄處理過的節(jié)點(diǎn)的數(shù)組
processed = []

# 定義尋找最小節(jié)點(diǎn)的函數(shù)
def find_lowest_cost_node(costs):
    lowest_cost = float("inf")
    lowest_cost_node = None
    for node in costs:  # 遍歷所有節(jié)點(diǎn)
        cost = costs[node]
        if cost < lowest_cost and node not in processed: # 如果當(dāng)前節(jié)點(diǎn)的開銷更低且未處理過
            lowest_cost = cost
            lowest_cost_node = node
    return lowest_cost_node

# 尋找最短路徑
def find_shortest_path():
    node = "fin"
    shortest_path = ["fin"]
    while parents[node] != "start":
        shortest_path.append(parents[node])
        node = parents[node]
    shortest_path.append("start")
    shortest_path.reverse()  # 將從終點(diǎn)到起點(diǎn)的路徑反序表示
    return shortest_path

# 狄克斯特拉算法尋找最短路徑
def dijkstra():
    node = find_lowest_cost_node(costs)  #在未處理的節(jié)點(diǎn)中找到開銷最小的節(jié)點(diǎn)
    while node is not None:   # 所有節(jié)點(diǎn)都被處理過，node為None，循環(huán)結(jié)束
        cost = costs[node]
        neighbors = graph[node]
        for n in neighbors.keys():  # 遍歷當(dāng)前節(jié)點(diǎn)的所有鄰居
            new_cost = cost + neighbors[n]
            if costs[n] > new_cost:  # 如果經(jīng)當(dāng)前節(jié)點(diǎn)前往該鄰居更近
                costs[n] = new_cost  # 就更新該鄰居的開銷
                parents[n] = node  # 同時(shí)將該鄰居的父節(jié)點(diǎn)設(shè)置為當(dāng)前節(jié)點(diǎn)
        processed.append(node)  # 將當(dāng)前節(jié)點(diǎn)標(biāo)記為處理過
        node = find_lowest_cost_node(costs)  # 找出接下來要處理的節(jié)點(diǎn)，并循環(huán)
    shortest_path = find_shortest_path()
    print(shortest_path)

# 運(yùn)行
dijkstra()
            
          

?

運(yùn)行結(jié)果為：

            
              ?['start', 'b', 'a', 'fin']
            
          

?

運(yùn)行后，內(nèi)部各變量的對(duì)應(yīng)信息如下：

            
              costs = {'a': 5, 'b': 2, 'fin': 6}

graph = {'start': {'a': 6, 'b': 2}, 'a': {'fin': 1}, 'b': {'a': 3, 'fin': 5}, 'fin': {}}

parents = {'a': 'b', 'b': 'start', 'fin': 'a'}

precessed = ['b', 'a', 'fin']
            
          

?

輔助說明：

（1）廣度優(yōu)先搜索用于在非加權(quán)圖中查找最短路徑

（2）狄克斯特拉算法用于在加權(quán)圖中查找最短路徑

（3）僅在權(quán)重為正時(shí)狄克斯特拉算法才管用

（4）如果圖中包含了負(fù)權(quán)邊（節(jié)點(diǎn)間開銷為負(fù)值），請(qǐng)使用貝爾曼-福德算法。