def find_lowest_cost_node(costs):
    lowest_cost = float("inf") # 設置初始開銷為無窮大，因為你現(xiàn)在很茫然
    lowest_cost_node = None # 設置初始最低開銷節(jié)點為 None
    for node in costs: # 遍歷所有的節(jié)點
        cost = costs[node]
        if cost < lowest_cost and node not in processed: # 如果當前節(jié)點的開銷更低且未處理過，
            lowest_cost = cost # 就將其視為開銷最低的節(jié)點。
            lowest_cost_node = node # 最低開銷節(jié)點為當前的節(jié)點。
    return lowest_cost_node

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

二、創(chuàng)建存儲父節(jié)點的散列表代碼如下：

parents = {}
parents["a"] = "start"
parents["b"] = "start"
parents["fin"] = None

三、創(chuàng)建一個數(shù)組，用于記錄處理過的節(jié)點，對于同一個節(jié)點，不用多次處理。

processed = []

四、按照算法列出代碼

node = find_lowest_cost_node(costs) # 在未處理的節(jié)點中找出開銷最小的節(jié)點
while node is None: # 這個 while 循環(huán)在所有節(jié)點都被處理過后結束
    cost = costs[node]
    neighbors = graph[node]
    for n in neighbors.keys(): # 遍歷當前節(jié)點的所有鄰居
        new_cost = cost + neighbors[n]
        if costs[n] > new_cost: # 如果經當前節(jié)點前往該鄰居最近，
            costs[n] = new_cost # 就更新該鄰居的開銷
            parents[n] = node # 同時將該鄰居的父節(jié)點設置為當前節(jié)點
    processed.append(node) # 將當前借調標記為已處理
    node = find_lowest_cost_node(costs) # 找出接下來要處理的節(jié)點，并循環(huán)。

在 Python 3.5.2 上親測有效。

# -*- coding:utf-8 -*-
__author__ = "東方鶚"
__blog__ = "www.os373.cn"

def find_lowest_cost_node(costs, processed):
    lowest_cost = float("inf") # 設置初始開銷為無窮大，因為你現(xiàn)在很茫然
    lowest_cost_node = None # 設置初始最低開銷節(jié)點為 None
    for node in costs: # 遍歷所有的節(jié)點
        cost = costs[node]
        if cost < lowest_cost and node not in processed: # 如果當前節(jié)點的開銷更低且未處理過，
            lowest_cost = cost # 就將其視為開銷最低的節(jié)點。
            lowest_cost_node = node # 最低開銷節(jié)點為當前的節(jié)點。
    return lowest_cost_node


def best_route():
    """ 存儲所有節(jié)點及其下一個節(jié)點開銷的字典 """
    graph = {"start": {"a": 6, "b": 2}, "a": {"fin": 1}, "b": {"a": 3, "fin": 5}, "fin": {}}

    """ 從起點開始，包含所有下一個節(jié)點開銷的字典 """
    infinity = float("inf")
    costs = {"a": 6, "b": 2, "fin": infinity}

    """ 從起點開始，存儲所有父節(jié)點的散列表 """

    parents = {"a": "start", "b": "start", "fin": None}
    best_route = ""
    processed = []

    node = find_lowest_cost_node(costs, processed) # 在未處理的節(jié)點中找出開銷最小的節(jié)點    
    while node is not None: # 這個 while 循環(huán)在所有節(jié)點都被處理過后結束
        cost = costs[node]
        neighbors = graph[node]
        for n in neighbors.keys(): # 遍歷當前節(jié)點的所有鄰居
            new_cost = cost + neighbors[n]
            if costs[n] > new_cost: # 如果經當前節(jié)點前往該鄰居最近，
                costs[n] = new_cost # 就更新該鄰居的開銷
                parents[n] = node # 同時將該鄰居的父節(jié)點設置為當前節(jié)點
        processed.append(node) # 將當前借調標記為已處理
        node = find_lowest_cost_node(costs, processed) # 找出接下來要處理的節(jié)點，并循環(huán)。
    
    p = parents["fin"]
    
    while True:  
        best_route += "%s<——" % p
        p = parents[p]
        
        if p is "start":
            break               
        
                
    return "到達終點的最終路徑是: 終點<——%s起點。
最快到達的時間是%s分鐘" % (best_route, costs["fin"])
        
if __name__ == "__main__":
    best_route = best_route()
    print(best_route)

結果如下：

到達終點的最終路徑是: 終點<——a<——b<——起點。
最快到達的時間是6分鐘

1、該算法只適用于有向無環(huán)圖！
2、該算法將 0 視作最小的權值，也就是說，如果出現(xiàn)負權值的情況，那么該算法將失效！

《算法圖解》

本人用C作的視頻，敬請點閱