一、簡介

是從一個頂點到其余各頂點的最短路徑算法，解決的是有向圖中最短路徑問題。迪杰斯特拉算法主要特點是以起始點為中心向外層層擴展，直到擴展到終點為止

二、步驟

(1) 找出“最便宜”的節點，即可在最短時間內到達的節點。
(2) 更新該節點的鄰居的開銷，其含義將稍后介紹。
(3) 重復這個過程，直到對圖中的每個節點都這樣做了。
(4) 計算最終路徑。

三、圖解

上圖中包括5個節點，箭頭表示方向，線上的數字表示消耗時間。
首先根據上圖做出一個初始表(父節點代表從哪個節點到達該節點)：

然后從“起點”開始，根據圖中的信息更新一下表，由于從“起點”不能直接到達“終點”節點，所以耗時為∞(無窮大)：

有了這個表我們可以根據算法的步驟往下進行了。

第一步：找出“最便宜”的節點，這里是節點B：

第二步：更新該節點的鄰居的開銷，根據圖從B出發可以到達A和“終點”節點，B目前的消耗2+B到A的消耗3=5，5小于原來A的消耗6，所以更新節點A相關的行：

同理，B目前消耗2+B到End的消耗5=7，小于∞，更新“終點”節點行：

B節點關聯的節點已經更新完成，所以B節點不在后面的更新范圍之內了：

找到下一個消耗最小的節點，那就是A節點：

根據A節點的消耗更新關聯節點，只有End節點行被更新了：

這時候A節點也不在更新節點范圍之內了：

最終表的數據如下：