摘要：致敬首先向偉大的牛人致敬使用狄克斯特拉算法如果所示找出從起點到終點耗時最短的路徑。狄克斯特拉算法思路步驟或思路如下找出最便宜的節點，即可在最短時間內前往的節點。

狄克斯特拉算法是一種實現了在有障礙物的兩個地點之間找出一條最短路徑的高效算法，解決了機器人學中的一個十分關鍵的問題，即運動路徑規劃問題，至今仍被廣泛應用。是“貪心方法（greedy method）”的一個成功范例。

首先向偉大的牛人致敬！

如果所示：

找出從起點到終點耗時最短的路徑。其中，每個數字表示的都是時間，單位分鐘。線路使用有方向的箭頭線路表示，表示只有一個方向可以使用，統稱有向圖。

為了找到從起點到終點耗時最短的路徑，我們通常需要找出從起點到終點所有的路徑，然后進行一一對比。

路徑一是從起點出發，經過 A 節點，到達終點，共計用時 6 + 1 = 7 分鐘。

路徑二是從起點出發，經過 B 節點，到達終點，共計用時 2 + 5 = 7 分鐘。

路徑三從起點出發，經過 B 節點，再經過 A 節點，到達終點，共計用時 2 + 3 + 1 = 6 分鐘。

綜上，我們已經窮舉完了所有可能的路徑，不可能再找出另外的路徑了。同時，對比一下三種路徑，你會發現路徑三用時最短，只需要 6 分鐘。呵呵，so easy，媽媽再也不用擔心我的學習了。既然，人可以做出結果，那么計算機利用此種方法，也就是所謂的窮舉法，當然也能找到最優路徑。

不過，別得意，你的媽媽還得擔心你的學習。如果路途中，不止 A、B 兩個節點，而是接近無窮多個節點，記住是接近無窮多個節點，......懵逼從天空飄過。

此時，肯定有同學會跳出來反對，無窮多個節點，這就是無限。無限，也就是無界，就是死循環的問題了，肯定無法得到答案，此題出得有問題。

這個問題提得好，必須有界才能有答案，該問題是接近無限多，也就是個很大很大的邊界，是超出了人力范圍的邊界。......懵逼繼續從天空飄過。 但是，計算機肯定是能夠計算出有界的問題的，利用窮舉法當然可以算出，不過這里又產生一個問題，窮舉法是檢索每條可能的路徑，這肯定會消耗很大的計算機運算能力，那么有沒有更優的方法，至少不用窮舉出所有路徑的方法呢？當然，有那么多的牛人供我們致敬，答案是肯定的。

步驟或思路如下：

找出最便宜的節點，即可在最短時間內前往的節點。

對于該節點的所有鄰居，檢查是否有前往它們的更短路徑，如果有，就更新其開銷。

處理過的節點，進行標記，以后將不再處理。

重復以上過程，直到對圖中的每個節點都這樣做了。

計算出最終路徑。

第一步：找出最便宜的節點。你站在起點，不知道該前往節點 A 還是節點 B ，茫然無措ing........。此時，散列表可以派上用場了。啥是散列表？你可以把它當做是一個列表，詳細的東西問谷歌，請自備梯子。

前往節點 A 需要6 分鐘，而前往節點 B 需要 2 分鐘。至于前往其它節點，你還不知道需要多長時間。那么散列表如下：

第二步：由于從起到到節點 B 的路徑耗時少，先計算經節點 B 前往其各個鄰居所需的時間。

這一步，找到了一條前往節點 A 的更短路徑！直接前往節點 A 需要 6 分鐘。但是經過節點 B 前往節點 A 只需要 5 分鐘。

對于節點 B 的鄰居，如果找到前往它的更短路徑，就更新其開銷。

前往節點 A 的更短路徑，時間從 6 分鐘縮短到 5 分鐘。

前往終點的更短路徑，時間從無窮大縮短到 7 分鐘。

第三步：對節點 B 已進行處理，所以要對節點 B 進行標記，以后將不再處理節點 B。

第四部： 重復！

重復第一步：找出可在最短時間內前往的節點。除節點 B 之外，可以在最短時間內前往的節點是節點 A 。
重復第二步：更新節點 A 的所有鄰居的開銷。

現在對每個節點都運行了狄克斯特拉算法（無需對終點這樣做）。現在，你知道：

前往節點 B 需要 2 分鐘；

前往節點A 需要 5 分鐘；

前往終點需要 6 分鐘。

所以你會發現，前往終點的時間為 6 分鐘！！！

def find_lowest_cost_node(costs):
    lowest_cost = float("inf") # 設置初始開銷為無窮大，因為你現在很茫然
    lowest_cost_node = None # 設置初始最低開銷節點為 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

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 = []

四、按照算法列出代碼

node = find_lowest_cost_node(costs) # 在未處理的節點中找出開銷最小的節點
while node is None: # 這個 while 循環在所有節點都被處理過后結束
    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) # 找出接下來要處理的節點，并循環。

在 Python 3.5.2 上親測有效。

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

def find_lowest_cost_node(costs, processed):
    lowest_cost = float("inf") # 設置初始開銷為無窮大，因為你現在很茫然
    lowest_cost_node = None # 設置初始最低開銷節點為 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 best_route():
    """ 存儲所有節點及其下一個節點開銷的字典 """
    graph = {"start": {"a": 6, "b": 2}, "a": {"fin": 1}, "b": {"a": 3, "fin": 5}, "fin": {}}

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

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

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

    node = find_lowest_cost_node(costs, processed) # 在未處理的節點中找出開銷最小的節點    
    while node is not None: # 這個 while 循環在所有節點都被處理過后結束
        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, processed) # 找出接下來要處理的節點，并循環。
    
    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、該算法只適用于有向無環圖！
2、該算法將 0 視作最小的權值，也就是說，如果出現負權值的情況，那么該算法將失效！

《算法圖解》

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