亚洲免费在线-亚洲免费在线播放-亚洲免费在线观看-亚洲免费在线观看视频-亚洲免费在线看-亚洲免费在线视频

Dijkstra算法的Python實現-最短路徑問題

系統 3245 0

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

Dijkstra算法的Python實現-最短路徑問題_第1張圖片

狄克斯特拉算法包含的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元等您想捐的金額吧,狠狠點擊下面給點支持吧,站長非常感激您!手機微信長按不能支付解決辦法:請將微信支付二維碼保存到相冊,切換到微信,然后點擊微信右上角掃一掃功能,選擇支付二維碼完成支付。

【本文對您有幫助就好】

您的支持是博主寫作最大的動力,如果您喜歡我的文章,感覺我的文章對您有幫助,請用微信掃描上面二維碼支持博主2元、5元、10元、自定義金額等您想捐的金額吧,站長會非常 感謝您的哦?。?!

發表我的評論
最新評論 總共0條評論
主站蜘蛛池模板: 天天干天天操天天射 | 国内精品久久久久久不卡影院 | 欧美成人高清免费大片观看 | 日韩一区二区三 | 视频在线欧美 | 99热久久免费精品首页 | 婷婷免费高清视频在线观看 | 91在线| 九九热线有精品视频99 | 午夜视频国产 | 久久精品五月天 | 国产美女久久久 | 欧美性猛交xxxxx按摩欧美 | 你懂的日韩 | 国产成人欧美 | 成人爽a毛片在线视频网站 成人爽视频 | 好色婷婷 | 天天视频国产免费入口 | 日韩深夜视频 | 天天摸天天爽天天澡视频 | 久久精品国产这里是免费 | 97 在线播放 | 国产高清视频在线播放 | 床上毛片 | 国产精品视频一区二区三区不卡 | 精品一区二区三区中文 | 国产探花在线观看 | 国产一区二区精品久久91 | 嫩草成人国产精品 | 中文字幕第66页永久乱码 | 欧美成人伦理 | 亚洲最色| 国产伦精品一区二区三区在线观看 | 国产高清一区二区三区视频 | 色综合天天综合网国产国产人 | 五月天色婷婷在线 | 国内精品久久久久久久久久久久 | 亚洲国产综合精品 | 99热这里都是国产精品 | 本日黄色| 久久精品中文字幕不卡一二区 |