前言
在學習廣度優先搜索的時候，你找出了從A點到B點的路徑。
這是最短路徑，因為段數最少——只有三段，但不一定是最快路徑。如果給這些路段加上時間，你將發現有更快的路徑。
如果你要找出最快的路徑，該如何辦呢？為此，可使用另一種算法——狄克斯特拉算法（Dijkstra’s algorithm）。
使用狄克斯特拉算法
下面來看看如何對下面的圖使用這種算法。
其中每個數字表示的都是時間，單位分鐘。為找出從起點到終點耗時最短的路徑，你將使用狄克斯特拉算法。
如果你使用廣度優先搜索，將得到下面這條段數最少的路徑。
這條路徑耗時7分鐘。下面來看看能否找到耗時更短的路徑！狄克斯特拉算法包含4個步驟。
- (1) 找出“最便宜”的節點，即可在最短時間內到達的節點。
- (2) 更新該節點的鄰居的開銷，其含義將稍後介紹。
- (3) 重複這個過程，直到對圖中的每個節點都這樣做了。
- (4) 計算最終路徑。
第一步：找出最便宜的節點。
你站在起點，不知道該前往節點A還是前往節點B。前往這兩個節點都要多長時間呢？
前往節點A需要6分鐘，而前往節點B需要2分鐘。至於前往其他節點，你還不知道需要多長時間。
由於你還不知道前往終點需要多長時間，因此你假設為無窮大（這樣做的原因你馬上就會明白）。節點B是最近的——2分鐘就能達到。
第二步：計算經節點B前往其各個鄰居所需的時間。
你剛找到了一條前往節點A的更短路徑！直接前往節點A需要6分鐘。
但經由節點B前往節點A只需5分鐘！
對於節點B的鄰居，如果找到前往它的更短路徑，就更新其開銷。在這裡，你找到了：
- 前往節點A的更短路徑（時間從6分鐘縮短到5分鐘）；
- 前往終點的更短路徑（時間從無窮大縮短到7分鐘）。
第三步：重複！
重複第一步：找出可在最短時間內前往的節點。你對節點B執行了第二步，除節點B外，可在最短時間內前往的節點是節點A。
重複第二步：更新節點A的所有鄰居的開銷。
你發現前往終點的時間為6分鐘！
你對每個節點都運行了狄克斯特拉算法（無需對終點這樣做）。現在，你知道：
- 前往節點B需要2分鐘；
- 前往節點A需要5分鐘；
- 前往終點需要6分鐘。
最後一步——計算最終路徑將留到下一節去介紹，這裡先直接將最終路徑告訴你。
如果使用廣度優先搜索，找到的最短路徑將不是這條，因為這條路徑包含3段，而有一條從起點到終點的路徑只有兩段。
在前一章，你使用了廣度優先搜索來查找兩點之間的最短路徑，那時“最短路徑”的意思是段數最少。在狄克斯特拉算法中，你給每段都分配了一個數字或權重，因此狄克斯特拉算法找出的是總權重最小的路徑。
這裡重述一下，狄克斯特拉算法包含4個步驟。
- (1) 找出最便宜的節點，即可在最短時間內前往的節點。
- (2) 對於該節點的鄰居，檢查是否有前往它們的更短路徑，如果有，就更新其開銷。
- (3) 重複這個過程，直到對圖中的每個節點都這樣做了。
- (4) 計算最終路徑。
實現
注意：
- 狄克斯特拉算法用於每條邊都有關聯數字的圖，這些數字稱為權重（weight）。
- 如果有負權邊，就不能使用狄克斯特拉算法。
下面來看看如何使用代碼來實現狄克斯特拉算法，這裡以下面的圖為例。
要編寫解決這個問題的代碼，需要三個散列表。
隨著算法的進行，你將不斷更新散列表costs和parents。首先，需要實現這個圖，為此可使用一個散列表。
在前一章中，你像下面這樣將節點的所有鄰居都存儲在散列表中。
graph[“you”] = [“alice”, “bob”, “claire”]
但這裡需要同時存儲鄰居和前往鄰居的開銷。例如，起點有兩個鄰居——A和B。
如何表示這些邊的權重呢？為何不使用另一個散列表呢？
因此graph[“start”]是一個散列表。要獲取起點的所有鄰居，可像下面這樣做。
有一條從起點到A的邊，還有一條從起點到B的邊。要獲悉這些邊的權重，該如何辦呢？
下面來添加其他節點及其鄰居。
graph[“a”] = {}
graph[“a”][“fin”] = 1
graph[“b”] = {}
graph[“b”][“a”] = 3
graph[“b”][“fin”] = 5
#終點沒有任何鄰居
graph[“fin”] = {}
表示整個圖的散列表類似於下面這樣。
接下來，需要用一個散列表來存儲每個節點的開銷。
節點的開銷指的是從起點出發前往該節點需要多長時間。你知道的，從起點到節點B需要2分鐘，從起點到節點A需要6分鐘（但你可能會找到所需時間更短的路徑）。你不知道到終點需要多長時間。對於還不知道的開銷，你將其設置為無窮大。在Python中能夠表示無窮大嗎？你可以這樣做：
infinity = float(“inf”)
創建開銷表的代碼如下：
infinity = float(“inf”)
costs = {}
costs[“a”] = 6
costs[“b”] = 2
costs[“fin”] = infinity
還需要一個存儲父節點的散列表：
創建這個散列表的代碼如下：
parents = {}
parents[“a”] = “start”
parents[“b”] = “start”
parents[“fin”] = None
最後，你需要一個數組，用於記錄處理過的節點，因為對於同一個節點，你不用處理多次。
processed = []
準備工作做好了，下面來看看算法。
我先列出代碼，然後再詳細介紹。代碼如下。
這就是實現狄克斯特拉算法的Python代碼！函數find_lowest_cost_node的代碼稍後列
出，我們先來看看這些代碼的執行過程。
找出開銷最低的節點。
獲取該節點的開銷和鄰居。
遍歷鄰居。
每個節點都有開銷。開銷指的是從起點前往該節點需要多長時間。在這裡，你計算從起點出發，經節點B前往節點A（而不是直接前往節點A）需要多長時間。
接下來對新舊開銷進行比較。
找到了一條前往節點A的更短路徑！因此更新節點A的開銷。
這條新路徑經由節點B，因此節點A的父節點改為節點B。
現在回到了for循環開頭。下一個鄰居是終點節點。
經節點B前往終點需要多長時間呢？
需要7分鐘。終點原來的開銷為無窮大，比7分鐘長。
設置終點節點的開銷和父節點。
你更新了節點B的所有鄰居的開銷。現在，將節點B標記為處理過。
找出接下來要處理的節點。
獲取節點A的開銷和鄰居。
節點A只有一個鄰居：終點節點。
當前，前往終點需要7分鐘。如果經節點A前往終點，需要多長時間呢？
經節點A前往終點所需的時間更短！因此更新終點的開銷和父節點。
處理所有的節點後，這個算法就結束了。希望前面對執行過程的詳細介紹讓你對這個算法有更深入的認識。函數find_lowest_cost_node找出開銷最低的節點，其代碼非常簡單，如下所示。
完整代碼如下：
閱讀更多 看到他請叫他快去學習 的文章
