戴克斯特拉算法

演算法描述

這個演算法是通過為每個頂點 v 保留目前為止所找到的從s到v的最短路徑來工作的。初始時，原點 s 的路徑權重被賦為 0 （d[s] = 0）。若對於頂點 m 存在能直接到達的邊（s,m），則把d[m]設為w（s, m）,同時把所有其他（s不能直接到達的）頂點的路徑長度設為無窮大，即表示我們不知道任何通向這些頂點的路徑（對於所有頂點的集合 V 中的任意頂點 v， 若 v 不為 s 和上述 m 之一， d[v] = ∞）。當演算法結束時，d[v] 中儲存的便是從 s 到 v 的最短路徑，或者如果路徑不存在的話是無窮大。
邊的拓展是Dijkstra 演算法的基礎操作：如果存在一條從 u 到 v 的邊，那麼從 s 到 v 的最短路徑可以通過將邊（u, v）添加到從 s 到 u 的路徑尾部來拓展一條從 s 到 v 的路徑。這條路徑的長度是 d[u] + w(u, v)。如果這個值比目前已知的 d[v] 的值要小，我們可以用新值來替代當前 d[v] 中的值。拓展邊的操作一直執行到所有的 d[v] 都代表從 s 到 v 的最短路徑的長度值。此演算法的組織令 d[u] 達到其最終值時，每條邊（u, v）都只被拓展一次。
演算法維護兩個頂點集合 S 和 Q。集合 S 保留所有已知最小 d[v] 值的頂點 v ，而集合 Q 則保留其他所有頂點。集合S初始狀態為空，而後每一步都有一個頂點從 Q 移動到 S。這個被選擇的頂點是 Q 中擁有最小的 d[u] 值的頂點。當一個頂點 u 從 Q 中轉移到了 S 中，演算法對 u 的每條外接邊 (u, v) 進行拓展。
下面的虛擬碼計算並保留圖G中原點s到每一頂點v的最短距離d[v]，同時找出並保留v在此最短路徑上的「前趨」，即沿此路徑由s前往v，到達v之前所到達的頂點。其中，函式Extract_Min(Q) 將頂點集合Q中有最小d[u]值的頂點u從Q中刪除並返回u。
 1  function Dijkstra(G, w, s)
 2     for each vertex v in V[G]        // 初始化
 3           d[v] := infinity           // 將各點的已知最短距離先設成無窮大
 4           previous[v] := undefined   // 各點的已知最短路徑上的前趨都未知
 5     d[s] := 0                        // 因為出發點到出發點間不需移動任何距離，所以可以直接將s到s的最小距離設為0
 6     S := empty set
 7     Q := set of all vertices
 8     while Q is not an empty set      // Dijkstra演算法主體
 9           u := Extract_Min(Q)
10           S.append(u)
11           for each edge outgoing from u as (u,v)
12                  if d[v] > d[u] + w(u,v)             // 拓展邊（u,v）。w(u,v)為從u到v的路徑長度。
13                        d[v] := d[u] + w(u,v)         // 更新路徑長度到更小的那個和值。
14                        previous[v] := u              // 紀錄前趨頂點
如果我們只對在 s 和 t 之間尋找一條最短路徑的話，我們可以在第9行添加條件如果滿足 u = t 的話終止程式。
通過推導可知，為了記錄最佳路徑的軌跡，我們只需記錄該路徑上每個點的前趨，即可通過疊代來回溯出 s 到 t 的最短路徑（當然，使用後繼節點來儲存亦可。但那需要修改程式碼）：
1 S := empty sequence 
2 u := t
3 while defined u                                        
4       insert u to the beginning of S
5       u := previous[u]      //previous陣列即為上文中的p
現在序列 S 就是從 s 到 t 的最短路徑的頂點集。

時間複雜度

我們可以用大O符號將該演算法的運行時間表示為邊數和頂點數的函式。
對於基於頂點集的實現，演算法的執行時間是，其中和分別表示完成鍵的降序排列時間和從中提取最小鍵值的時間。
Dijkstra演算法最簡單的實現方法是用一個連結串列或者數組來儲存所有頂點的集合，所以搜尋中最小元素的運算（Extract-Min()）只需要線性搜尋 中的所有元素。這樣的話演算法的運行時間是。
對於邊數少於的稀疏圖來說，我們可以用鄰接表來更有效的實現該演算法。同時需要將一個二元堆積或者斐波納契堆用作優先隊列來尋找最小的頂點（Extract-Min）。當用到二元堆積的時候，演算法所需的時間為，斐波納契堆能稍微提高一些效能，讓演算法運行時間達到。然而，使用斐波納契堆進行編程，常常會由於演算法常數過大而導致速度沒有顯著提高。

相關問題及演算法

開放最短路徑優先演算法是該演算法在網路路由中的一個具體實現。
與 Dijkstra 演算法不同，Bellman-Ford演算法可用於具有負花費邊的圖，只要圖中不存在總花費為負值且從源點 s 可達的環路（如果有這樣的環路，則最短路徑不存在，因為沿環路循環多次即可無限制的降低總花費）。在可能有環路的情況下，Bellman-Ford演算法則可以通過檢測程式while迴圈次數是否大於|V|來進行判斷。 
與最短路徑問題相關最有名的一個問題是旅行商問題，此類問題要求找出恰好通過所有目標點一次且最終回到原點的最短路徑。然而該問題為NP-完全的；換言之，與最短路徑問題不同，旅行商問題不太可能具有多項式時間解法。
如果有已知資訊可用來估計某一點到目標點的距離，則可改用A*搜尋演算法，以減小最短路徑的搜尋範圍。

參考源程式

1 #include <iostream> 2 #include <cstdio> 3 #include <cstdlib> 4 #include <cmath> 5 #include <queue> 6 using namespace std; 7  8 const int maxn = 500000 + 100; 9 10 struct edge {11 int v, w, next;12 edge(int v=0, int w=0, int next=0) : v(v), w(w), next(next) {13 }14 }e[maxn];15 int front[maxn], tot=0;16 17 void Addedge(int u, int v, int w) {18 tot++;19 e[tot].v = v;20 e[tot].w = w;21 e[tot].next = front[u];22 front[u] = tot;23 }24 25 int N, M, S;26 27 void Readin() {28 ios::sync_with_stdio(false);29 cin >> N >> M >> S;30 for(int i = 1; i <= M; i++) {31 int u, v, w;32 cin >> u >> v >> w;33 Addedge(u, v, w);34 }35 }36 37 struct Heap {38 int id, w;39 bool operator < (const Heap &rhs) const {40 return w < rhs.w;41 }42 };43 44 int dis[maxn];45 int Dijkstra(int s) {46 priority_queue<Heap> q;47 for(int i = 1; i <= N; i++) dis[i] = 2147483647;48 dis[s] = 0;49 q.push(Heap{s, dis[s]});50 while(!q.empty()) {51 Heap x = q.top(); q.pop();52 if(dis[x.id] != x.w) continue;53 for(int i = front[x.id]; i != 0; i = e[i].next) {54 int k = e[i].v;55 if(dis[k] > dis[x.id] + e[i].w) {56 dis[k] = dis[x.id] + e[i].w;57 q.push(Heap{k, dis[k]});58 }59 }60 }61 for(int i =  1; i <= N; i++) cout << dis[i] << ' ';62 cout << endl;63 return 0;64 }