什麼是戴克斯特拉演算法
在邊的權重都在0以上的圖中，求從一個起點到各頂點最短路徑的演算法。反覆確定距離尚未確定的頂點中最近的一個，並更新其相鄰頂點的距離。有負權重的邊時無法正確求出。
日文名稱: ダイクストラ法
「戴克斯特拉演算法」出現在1領域的3道練習題中（資料結構與演算法等）。
這個名詞所屬的領域: 資料結構與演算法
步驟
把起點的距離設為0、其他頂點設為無限大，所有頂點設為未確定。從未確定的頂點中選出距離最小者並確定，對從該頂點出發的每條邊，若「確定的距離 + 邊的權重」小於另一端頂點目前的距離，就加以更新（鬆弛）。重複此步驟直到所有頂點都確定為止。更新時若記錄前一個頂點，之後就能追溯出最短路徑本身。
複雜度與優先佇列
若每次都從所有頂點中找出最小者，對頂點數 V 需要 O(V²)。使用以二元堆積實作的優先佇列，設邊數為 E，則變成 O((V + E) log V)，對道路網這類邊較少的圖會快得多。圖通常以鄰接串列保存。汽車導航的路徑搜尋，會結合加上到目的地估計距離、把搜尋範圍收斂到目的地方向的 A* 搜尋，以及使用預先計算資訊的加速手法。
負權重與其他演算法
戴克斯特拉演算法是在「經由其他頂點時距離只會增加、不會減少」的前提下確定頂點，因此有負權重的邊時，已確定的距離之後可能變短，無法保證正確答案。有負權重時，使用把所有邊的鬆弛重複 V−1 次的貝爾曼-福特演算法，也能偵測負環路。求所有頂點對之間的最短路徑，也會使用基於動態規劃的 Floyd-Warshall 演算法（O(V³)）。在網路路由中，OSPF 等鏈路狀態型協定會在各路由器以戴克斯特拉演算法計算路徑。
練習戴克斯特拉演算法的題目
在無向圖中，各邊的權重（距離）為 S−A: 4、S−B: 1、A−B: 2、A−C: 1、B−C: 5、C−T: 3、A−T: 6。以戴克斯特拉演算法求從 S 到 T 的最短路徑時，路徑與長度為下列何者？
- AS→A→C→T，長度8
- BS→B→A→C→T，長度7
- CS→B→C→T，長度9
查看答案與解析
正確答案：B. S→B→A→C→T，長度7
戴克斯特拉演算法反覆確定距離尚未確定的頂點中最近的一個，並更新其相鄰頂點的距離。從 S（0）開始，B 以1確定，經由 B 到 A 為 1 + 2 = 3，比直接的4短。確定 A（3）後，C 為 3 + 1 = 4、T 為 3 + 6 = 9；確定 C（4）後，T 更新為 4 + 3 = 7。因此最短路徑為 S→B→A→C→T，長度為7。S→A→C→T（8）因直接走 S−A 而較長，S→B→C→T（9）則因 B−C 的5較大而較長。
要以戴克斯特拉演算法求出正確的最短路徑，關於圖的條件，下列何者正確？
- A圖中沒有環路（回到同一頂點的路徑）
- B邊沒有方向
- C所有邊的權重都在0以上
查看答案與解析
正確答案：C. 所有邊的權重都在0以上
戴克斯特拉演算法會確定未確定頂點中距離最小者。這是基於「經由其他頂點時距離只會增加、不會減少」的前提。若有負權重的邊，之後可能經由其他路徑使距離變短；例如在 S→A 為2、S→B 為3、B→A 為−2 的有向圖中，A 以2確定之後，才找到 S→B→A 的1。有負權重時，要使用貝爾曼-福特演算法等方法。即使有環路或邊有方向，只要權重都在0以上，就能使用戴克斯特拉演算法。
常見問題
戴克斯特拉演算法與廣度優先搜尋有什麼關係？
若所有邊的權重都是1，戴克斯特拉演算法確定頂點的順序與廣度優先搜尋相同。可以把它看成是為了處理不同權重，而以依距離由小到大取出的優先佇列取代佇列的一般化。
戴克斯特拉演算法能用於有方向的圖嗎？
可以。只要權重在0以上，無論是有向圖或無向圖，即使有環路也能求出正確的最短路徑。
解析中的「戴克斯特拉演算法」
戴克斯特拉演算法反覆確定距離尚未確定的頂點中最近的一個，並更新其相鄰頂點的距離。
在無向圖中，各邊的權重（距離）為 S−A: 4、S−B: 1、A−B: 2、A−C: 1、B−C: 5、C−T: 3、…戴克斯特拉演算法會確定未確定頂點中距離最小者。
要以戴克斯特拉演算法求出正確的最短路徑，關於圖的條件，下列何者正確？對於像廣度優先搜尋或戴克斯特拉演算法這樣依序走訪從頂點出發之邊的處理，鄰接串列的效率較好。
像頂點約100萬個、邊約300萬條的道路網這樣，邊數相對於頂點數很少的（稀疏）圖，適合以下列何種方式存放在記憶體中？