算法簡介
迪科斯徹算法的輸入包含了一個有權重的有向圖 G，以及G中的一個來源頂點 S。我們以 V 表示 G 中所有頂點的集合。每一個圖中的邊，都是兩個頂點所形成的有序元素對。(u, v) 表示從頂點 u 到 v 有路徑相連。我們以 E 所有邊的集合，而邊的權重則由權重函式 w: E → [0, ∞] 定義。因此，w(u, v) 就是從頂點 u 到頂點 v 的非負花費值（cost）。邊的花費可以想像成兩個頂點之間的距離。任兩點間路徑的花費值，就是該路徑上所有邊的花費值總和。已知有 V 中有頂點 s 及 t，Dijkstra 算法可以找到 s 到 t 的最低花費路徑(例如，最短路徑)。這個算法也可以在一個圖中，找到從一個頂點 s 到任何其他頂點的最短路徑。算法描述
這個算法是通過為每個頂點 v 保留目前為止所找到的從s到v的最短路徑來工作的。初始時，原點 s 的路徑長度值被賦為 0 （d[s] = 0），同時把所有其他頂點的路徑長度設為無窮大，即表示我們不知道任何通向這些頂點的路徑（對於 V 中所有頂點 v 除 s 外d[v] = ∞）。當算法結束時，d[v] 中儲存的便是從 s 到 v 的最短路徑，或者如果路徑不存在的話是無窮大。 Dijkstra 算法的基礎操作是邊的拓展：如果存在一條從 u 到 v 的邊，那么從 s 到 v 的最短路徑可以通過將邊（u, v）添加到尾部來拓展一條從 s 到 u 的路徑。這條路徑的長度是 d[u] + w(u, v)。如果這個值比目前已知的 d[v] 的值要小，我們可以用新值來替代當前 d[v] 中的值。拓展邊的操作一直執行到所有的 d[v] 都代表從 s 到 v 最短路徑的花費。這個算法經過組織因而當 d[u] 達到它最終的值的時候每條邊（u, v）都只被拓展一次。算法維護兩個頂點集 S 和 Q。集合 S 保留了我們已知的所有 d[v] 的值已經是最短路徑的值頂點，而集合 Q 則保留其他所有頂點。集合S初始狀態為空，而後每一步都有一個頂點從 Q 移動到 S。這個被選擇的頂點是 Q 中擁有最小的 d[u] 值的頂點。當一個頂點 u 從 Q 中轉移到了 S 中，算法對每條外接邊 (u, v) 進行拓展。
時間複雜度
我們可以用大O符號將迪科斯徹算法的運行時間表示為邊數 m 和頂點數 n 的函式。Dijkstra 算法最簡單的實現方法是用一個鍊表或者數組來存儲所有頂點的集合 Q，所以搜尋 Q 中最小元素的運算（Extract-Min(Q)）只需要線性搜尋 Q 中的所有元素。這樣的話算法的運行時間是 O(n2)。
對於邊數少於 n2 的稀疏圖來說，我們可以用鄰接表來更有效的實現迪科斯徹算法。同時需要將一個二叉堆或者斐波納契堆用作優先佇列來尋找最小的頂點（Extract-Min）。當用到二叉堆的時候，算法所需的時間為O((m + n)log n)，斐波納契堆能稍微提高一些性能，讓算法運行時間達到O(m + n log n)。
相關問題及算法
原本的迪科斯徹算法還能夠加以修改以擴充其功能。舉例來說，面對一個問題，有時我們可能希望取得數學上的次佳解。為了求得這些次佳解，首先先用原本的迪科斯徹算法求出最佳路徑；接下來，我們移除最佳路徑中任一段路徑，並對剩下來的子集合圖再做一次最佳路徑計算。對於最佳路徑上的每一段路徑做一樣的操作，我們可以得到許多次佳路徑解，將這些路徑排序後即為原路徑問題的次佳路徑解集合。開放最短路徑優先（OSPF, Open Shortest Path First）算法是迪科斯徹算法在網路路由中的一個具體實現。
與 Dijkstra 算法不同，Bellman-Ford算法可用於具有負花費邊的圖，只要圖中不存在總花費為負值且從源點 s 可達的環路（如果有這樣的環路，則最短路徑不存在，因為沿環路循環多次即可無限制的降低總花費）。
與最短路徑問題相關最有名的一個問題是旅行商問題（Traveling salesman problem），此類問題要求找出恰好通過所有目標點一次且最終回到原點的最短路徑。然而該問題為NP-完全的；換言之，與最短路徑問題不同，旅行商問題不太可能具有多項式時間解法。
如果有已知信息可用來估計某一點到目標點的距離，則可改用A*搜尋算法，以減小最短路徑的搜尋範圍。
參考
E. W. Dijkstra: A note on two problems in connexion with graphs. In: Numerische Mathematik. 1 (1959), S. 269–271Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Section 24.3: Dijkstra's algorithm, pp.595–601.
