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

狄克斯特拉算法包含的4個步驟：

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

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

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

（4）計算最終路徑

?

python代碼實現(xiàn)：

            
              # 描述各節(jié)點、時間開銷、父節(jié)點信息
# 創(chuàng)建節(jié)點信息，start起點，fin終點
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)建開銷/時間表
infinity = float("inf") #無窮大
costs={}
costs["a"]=6
costs["b"]=2
costs["fin"]=infinity   #暫時將通往終點的時間，定義為無窮大

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

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

# 定義尋找最小節(jié)點的函數(shù)
def find_lowest_cost_node(costs):
    lowest_cost = float("inf")
    lowest_cost_node = None
    for node in costs:  # 遍歷所有節(jié)點
        cost = costs[node]
        if cost < lowest_cost and node not in processed: # 如果當(dāng)前節(jié)點的開銷更低且未處理過
            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()  # 將從終點到起點的路徑反序表示
    return shortest_path

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

# 運行
dijkstra()
            
          

?

運行結(jié)果為：

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

?

運行后，內(nèi)部各變量的對應(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)重為正時狄克斯特拉算法才管用

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