狄克斯特拉算法包含四個步驟：

1·找出“最便宜的節點，即可在最短時間內到達的節點”

2·更新該節點的鄰居的開銷

3·重復這個過程，直到對圖中的每個節點都這樣做

4·計算最終路徑

1·第一步：找出最便宜的節點。你現在站在起點，不知道應該前往A節點還是B節點，那么前往這兩個節點應該花費多長時間呢？（開始選定一個起點）假設前往節點A需要6分鐘，而前往節點B需要2分鐘，至于前往A和B之后的那些節點要花費的時間，現在你還不知道，而且由于你還不知道前往終點的時間，因此你假設為無窮大?，F在來看從起點前往節點B是最短的用時（2分鐘）

2·第二步：計算經節點B前往它的各個鄰居需要花費的時間。對于節點B的鄰居，如果找到前往它的更短的路徑，就更新其開銷

3·第三步：重復。重復第一步：找出可在最短時間內前往的節點，你現在對節點B執行了第二步，除了節點B外，可在最短時間內前往的節點是節點A。重復第二步：更新節點A的所有鄰居的開銷

當你對每個節點都使用狄克斯特拉算法，你會發現

1·從起點前往節點B需要2分鐘

2·從節點B前往節點A需要5分鐘

3·從節點A前往終點需要6分鐘

# 需要注意的是：如果我們使用廣度優先搜索，找到的“最短路徑”將不是上述的這條，因為這條路包含了3段，而重新來看的話有一條路徑從起點到終點一共只有2段

# 我們使用廣度優先搜索來查找2點之間的最短路徑，那時的“最短路徑”的意思是段數最少。而在狄克斯特拉算法中，給每一段路徑都分配了一個“時間數值”因此狄克斯特拉算法找出的是總權重最小的路徑

# 狄克斯特拉算法背后的關鍵理念是：找出圖中最便宜的節點，并確保沒有到該節點更短的路徑

# 當然這里所說的最短路徑并不一定指的是物理距離，也可能是讓某種度量指標最小

再重復一下狄克斯特拉算法的4個步驟：

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

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

3·重復這個過程，直到對途中的每個節點都這樣做了

4·計算最終路徑（后面的隨筆會解釋是如何計算最終路徑的）

分析與起點（令起點為父節點）相連的幾條岔路后，再確定第二個隘口（記錄花銷）（將第二個隘口作為新的父節點，后面同理），之后再分析從第二個隘口前往第三個（也是分析與第二個隘口相連的幾條岔路后決定第三個隘口）隘口的花銷......重復上述步驟，直到到達終點，將前面從起點到第二個隘口，從第二個隘口到第三個隘口，等等的花銷進行累加。

當“順序走完全程”并進行逐路分析后，為了確定最終的路徑，由終點，一個隘口，一個隘口的進行回溯，最終到達起點，才能確定最終的路線（即由子節點找父節點）

# 實現代碼如下：