戴克斯特拉算法

算法描述

这个算法是通过为每个顶点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 }