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

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條評論
主站蜘蛛池模板: 久久精品视频16 | 国产精品成人在线播放 | 四虎影视永久地址 | 久久青草社区 | 中文字幕日本一区波多野不卡 | 中文字幕一区二区在线视频 | 天天看天天射天天碰 | 国产欧美精品一区二区三区-老狼 | 欧美草草 | 日日操天天 | 99久久综合狠狠综合久久一区 | 色婷婷5月精品久久久久 | 色黄网站青青草原免费 | 欧美黄色免费在线观看 | 欧美色99| 尹人香蕉99久久综合网站 | 欧美视频在线一区二区三区 | 全部免费毛片在线 | 欧美手机手机在线视频一区 | 一级做a爱片久久蜜桃 | 四虎影视在线影院在线观看 | 国产精品九九久久精品女同 | 精品久久在线 | 成人午夜天 | 91精品国产人成网站 | 午夜色站| 国产精品久久99 | 午夜一级精品免费毛片 | 欧美亚洲日本在线 | 国内在线观看 | 久久欧美精品欧美九久欧美 | 免费福利影院 | 国产精品99精品久久免费 | 免费观看日本污污ww网站精选 | 欧美一级毛片欧美一级无片 | 国产爆操| 男女一级免费视频 | 亚洲黄色激情视频 | 国产成人久久精品麻豆二区 | 女人18特级一级毛片免费视频 | 日本中文一区 |