人工智慧/搜尋/迪傑斯特拉演算法
迪傑斯特拉演算法用於圖搜尋。它是最佳的，這意味著它將找到最短的路徑。它是無資訊的，這意味著它不需要在事先知道目標節點。事實上，它找到了從每個節點到源節點的最短路徑。迪傑斯特拉演算法有很多可能的變化，針對特定目的進行了最佳化。一個例子是，如果已知目標節點，演算法可以被指示一旦找到該節點的最短路徑就終止。迪傑斯特拉演算法可以被認為是一種啟發式搜尋，類似於貪婪搜尋，如果搜尋有一個已知目標，並且可以被認為是一種窮舉搜尋，當搜尋沒有目標節點並且所有節點都被考慮時。迪傑斯特拉演算法的效率使其成為網路路由協議的最佳選擇。由於本質上任何組合最佳化問題都可以被表述為最短路徑問題，因此迪傑斯特拉演算法對於人工智慧研究也很重要。
迪傑斯特拉演算法需要一個源節點來開始。它將找到從該源節點到所有其他節點的最短距離。對於每個節點，它需要記憶體來儲存一個距離值和一個標記節點已訪問或未訪問的標誌。它還需要一個指標來跟蹤當前節點。
- 將源節點分配為距離值零，並將所有其他節點分配為距離值無窮大。
- 將所有節點標記為未訪問，並將源節點設定為當前節點。
- 對於當前節點，考慮其所有未訪問的鄰居，並使用經過當前節點的路徑計算其與源節點的距離。如果透過包含當前節點的路徑計算出的未訪問鄰居的距離小於其距離值，則使用新值覆蓋距離值。
- 噹噹前節點的所有鄰居都被考慮後，將當前節點標記為已訪問。已訪問的節點將永遠不會再次被檢查，其值是最終的，也是最小的。
- 將具有最低距離值的未訪問節點設定為當前節點，並從步驟 3 繼續。
（本節直接取自維基百科）在以下演算法中，程式碼 u := node in Q with smallest dist[]，搜尋具有最小 dist[u] 值的頂點集 Q 中的頂點 u。該頂點從頂點集 Q 中移除並返回給使用者。dist_between(u, v) 計算兩個相鄰節點 u 和 v 之間的長度。第 11 行的 alt 是從根節點到相鄰節點 v 的路徑的長度，如果它要經過 u。如果這條路徑比 v 當前記錄的最短路徑短，則用這條 alt 路徑替換當前路徑。previous 陣列填充了一個指向源圖上“下一個躍點”節點的指標，以獲得到源節點的最短路線。
1 function Dijkstra(Graph, source):
2 for each vertex v in Graph: // Initializations
3 dist[v] := infinity // Unknown distance function from source to v
4 previous[v] := undefined // Previous node in optimal path from source
5 dist[source] := 0 // Distance from source to source
6 Q := the set of all nodes in Graph
// All nodes in the graph are unoptimized - thus are in Q
7 while Q is not empty: // The main loop
8 u := vertex in Q with smallest dist[]
9 if dist[u] = infinity:
10 break // all remaining vertices are inaccessible
11 remove u from Q
12 for each neighbor v of u: // where v has not yet been removed from Q.
13 alt := dist[u] + dist_between(u, v)
14 if alt < dist[v]: // Relax (u,v,a)
15 dist[v] := alt
16 previous[v] := u
17 return previous[]
如果我們只對頂點 source 和 target 之間的最短路徑感興趣，則如果 u = target，我們可以線上 10 終止搜尋。現在，我們可以透過迭代讀取從 source 到 target 的最短路徑
1 S := empty sequence 2 u := target 3 while previous[u] is defined: 4 insert u at the beginning of S 5 u := previous[u]
現在序列 S 是構成從 target 到 source 的最短路徑之一的頂點列表，或者如果不存在路徑則為空序列。
一個更普遍的問題是找到 source 和 target 之間的所有最短路徑（可能存在多個具有相同長度的不同路徑）。然後，而不是在 previous[] 的每個條目中只儲存單個節點，而是儲存滿足鬆弛條件的所有節點。例如，如果 r 和 source 都連線到 target，並且它們都位於透過 target 的不同最短路徑上（因為兩種情況下的邊成本相同），那麼我們將 r 和 source 都新增到 previous[target] 中。當演算法完成時，previous[] 資料結構實際上將描述一個圖，它是原始圖的子集，其中一些邊已刪除。它的關鍵屬性是，如果演算法以某個起始節點執行，則從該節點到新圖中任何其他節點的任何路徑將是原始圖中這些節點之間的最短路徑，並且原始圖中所有具有該長度的路徑都將存在於新圖中。然後，為了實際找到這兩個給定節點之間的所有這些短路徑，我們將使用一種路徑查詢演算法在新圖上，例如深度優先搜尋。
- Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest 和 Clifford Stein。演算法導論，第二版。麻省理工學院出版社和麥格勞-希爾，2001。 ISBN 0-262-03293-7。第 24.3 節：迪傑斯特拉演算法，第 595-601 頁。
- 維基百科 (2009/03/11)。 http://en.wikipedia.org/wiki/Dijkstra's_algorithm
- 迪傑斯特拉演算法再探：OR/MS 連線 (2009/04/11)。 http://www.ifors.ms.unimelb.edu.au/tutorial/dijkstra_new/index.html