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

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

（1）找出開銷/消耗“最便宜”的節點，即在最短時間內到達的節點

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

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

（4）計算最終路徑

?

python代碼實現：

            
              # 描述各節點、時間開銷、父節點信息
# 創建節點信息，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"]={}

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

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

# 記錄處理過的節點的數組
processed = []

# 定義尋找最小節點的函數
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

# 尋找最短路徑
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)  #在未處理的節點中找到開銷最小的節點
    while node is not None:   # 所有節點都被處理過，node為None，循環結束
        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)  # 找出接下來要處理的節點，并循環
    shortest_path = find_shortest_path()
    print(shortest_path)

# 運行
dijkstra()
            
          

?

運行結果為：

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

?

運行后，內部各變量的對應信息如下：

            
              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）廣度優先搜索用于在非加權圖中查找最短路徑

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

（3）僅在權重為正時狄克斯特拉算法才管用

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