使用狄克斯特拉算法找出下圖中從起點至終點耗時最短的路徑,路徑上的每個數字表示的都是時間,單位分鐘。
狄克斯特拉算法包含的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)如果圖中包含了負權邊(節點間開銷為負值),請使用貝爾曼-福德算法。
更多文章、技術交流、商務合作、聯系博主
微信掃碼或搜索:z360901061

微信掃一掃加我為好友
QQ號聯系: 360901061
您的支持是博主寫作最大的動力,如果您喜歡我的文章,感覺我的文章對您有幫助,請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧,狠狠點擊下面給點支持吧,站長非常感激您!手機微信長按不能支付解決辦法:請將微信支付二維碼保存到相冊,切換到微信,然后點擊微信右上角掃一掃功能,選擇支付二維碼完成支付。
【本文對您有幫助就好】元
