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

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

首先向偉大的牛人致敬！

如果所示：

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

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

路徑一是從起點(diǎn)出發(fā)，經(jīng)過 A 節(jié)點(diǎn)，到達(dá)終點(diǎn)，共計(jì)用時 6 + 1 = 7 分鐘。

路徑二是從起點(diǎn)出發(fā)，經(jīng)過 B 節(jié)點(diǎn)，到達(dá)終點(diǎn)，共計(jì)用時 2 + 5 = 7 分鐘。

路徑三從起點(diǎn)出發(fā)，經(jīng)過 B 節(jié)點(diǎn)，再經(jīng)過 A 節(jié)點(diǎn)，到達(dá)終點(diǎn)，共計(jì)用時 2 + 3 + 1 = 6 分鐘。

綜上，我們已經(jīng)窮舉完了所有可能的路徑，不可能再找出另外的路徑了。同時，對比一下三種路徑，你會發(fā)現(xiàn)路徑三用時最短，只需要 6 分鐘。呵呵，so easy，媽媽再也不用擔(dān)心我的學(xué)習(xí)了。既然，人可以做出結(jié)果，那么計(jì)算機(jī)利用此種方法，也就是所謂的窮舉法，當(dāng)然也能找到最優(yōu)路徑。

不過，別得意，你的媽媽還得擔(dān)心你的學(xué)習(xí)。如果路途中，不止 A、B 兩個節(jié)點(diǎn)，而是接近無窮多個節(jié)點(diǎn)，記住是接近無窮多個節(jié)點(diǎn)，......懵逼從天空飄過。

此時，肯定有同學(xué)會跳出來反對，無窮多個節(jié)點(diǎn)，這就是無限。無限，也就是無界，就是死循環(huán)的問題了，肯定無法得到答案，此題出得有問題。

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

步驟或思路如下：

找出最便宜的節(jié)點(diǎn)，即可在最短時間內(nèi)前往的節(jié)點(diǎn)。

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

處理過的節(jié)點(diǎn)，進(jìn)行標(biāo)記，以后將不再處理。

重復(fù)以上過程，直到對圖中的每個節(jié)點(diǎn)都這樣做了。

計(jì)算出最終路徑。

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

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

第二步：由于從起到到節(jié)點(diǎn) B 的路徑耗時少，先計(jì)算經(jīng)節(jié)點(diǎn) B 前往其各個鄰居所需的時間。

這一步，找到了一條前往節(jié)點(diǎn) A 的更短路徑！直接前往節(jié)點(diǎn) A 需要 6 分鐘。但是經(jīng)過節(jié)點(diǎn) B 前往節(jié)點(diǎn) A 只需要 5 分鐘。

對于節(jié)點(diǎn) B 的鄰居，如果找到前往它的更短路徑，就更新其開銷。

前往節(jié)點(diǎn) A 的更短路徑，時間從 6 分鐘縮短到 5 分鐘。

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

第三步：對節(jié)點(diǎn) B 已進(jìn)行處理，所以要對節(jié)點(diǎn) B 進(jìn)行標(biāo)記，以后將不再處理節(jié)點(diǎn) B。

第四部： 重復(fù)！

重復(fù)第一步：找出可在最短時間內(nèi)前往的節(jié)點(diǎn)。除節(jié)點(diǎn) B 之外，可以在最短時間內(nèi)前往的節(jié)點(diǎn)是節(jié)點(diǎn) A 。
重復(fù)第二步：更新節(jié)點(diǎn) A 的所有鄰居的開銷。

現(xiàn)在對每個節(jié)點(diǎn)都運(yùn)行了狄克斯特拉算法（無需對終點(diǎn)這樣做）?，F(xiàn)在，你知道：

前往節(jié)點(diǎn) B 需要 2 分鐘；

前往節(jié)點(diǎn)A 需要 5 分鐘；

前往終點(diǎn)需要 6 分鐘。

所以你會發(fā)現(xiàn)，前往終點(diǎn)的時間為 6 分鐘?。?！

def find_lowest_cost_node(costs):
    lowest_cost = float("inf") # 設(shè)置初始開銷為無窮大，因?yàn)槟悻F(xiàn)在很茫然
    lowest_cost_node = None # 設(shè)置初始最低開銷節(jié)點(diǎn)為 None
    for node in costs: # 遍歷所有的節(jié)點(diǎn)
        cost = costs[node]
        if cost < lowest_cost and node not in processed: # 如果當(dāng)前節(jié)點(diǎn)的開銷更低且未處理過，
            lowest_cost = cost # 就將其視為開銷最低的節(jié)點(diǎn)。
            lowest_cost_node = node # 最低開銷節(jié)點(diǎn)為當(dāng)前的節(jié)點(diǎn)。
    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"] = {} # 終點(diǎn)沒有任何鄰居

表示整個圖的散列表類似下面這樣。

一、創(chuàng)建從起點(diǎn)開始的開銷表代碼如下：

infinity = float("inf")
costs = {}
costs["a"] = 6
costs["b"] = 2
costs["fin"] = infinity

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

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

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

processed = []

四、按照算法列出代碼

node = find_lowest_cost_node(costs) # 在未處理的節(jié)點(diǎn)中找出開銷最小的節(jié)點(diǎn)
while node is None: # 這個 while 循環(huán)在所有節(jié)點(diǎn)都被處理過后結(jié)束
    cost = costs[node]
    neighbors = graph[node]
    for n in neighbors.keys(): # 遍歷當(dāng)前節(jié)點(diǎn)的所有鄰居
        new_cost = cost + neighbors[n]
        if costs[n] > new_cost: # 如果經(jīng)當(dāng)前節(jié)點(diǎn)前往該鄰居最近，
            costs[n] = new_cost # 就更新該鄰居的開銷
            parents[n] = node # 同時將該鄰居的父節(jié)點(diǎn)設(shè)置為當(dāng)前節(jié)點(diǎn)
    processed.append(node) # 將當(dāng)前借調(diào)標(biāo)記為已處理
    node = find_lowest_cost_node(costs) # 找出接下來要處理的節(jié)點(diǎn)，并循環(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") # 設(shè)置初始開銷為無窮大，因?yàn)槟悻F(xiàn)在很茫然
    lowest_cost_node = None # 設(shè)置初始最低開銷節(jié)點(diǎn)為 None
    for node in costs: # 遍歷所有的節(jié)點(diǎn)
        cost = costs[node]
        if cost < lowest_cost and node not in processed: # 如果當(dāng)前節(jié)點(diǎn)的開銷更低且未處理過，
            lowest_cost = cost # 就將其視為開銷最低的節(jié)點(diǎn)。
            lowest_cost_node = node # 最低開銷節(jié)點(diǎn)為當(dāng)前的節(jié)點(diǎn)。
    return lowest_cost_node


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

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

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

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

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

結(jié)果如下：

到達(dá)終點(diǎn)的最終路徑是: 終點(diǎn)<——a<——b<——起點(diǎn)。
最快到達(dá)的時間是6分鐘

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

《算法圖解》

本人用C作的視頻，敬請點(diǎn)閱