算法描述

  上图为 戴克斯特拉算法 应用示意图。起点以左下角的红点 ， 目标是右上角的绿点 ， 中间灰色的倒L型为障碍物 。 蓝色空圈表示"暂定" ，用以搜索下一步；已经填充颜色的表示探访过，图中颜色以红到绿，越绿表示离起点越远。所有节点都被均匀的探索。

这个算法是通过为每个顶点 v 保留目前为止所找到的从s到v的最短路径来工作的。初始时，原点 s 的路径权重被赋为 0 （ d[s] = 0）。若对于顶点 s 存在能直接到达的边（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 到 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。

如果我们只对在 s 和 t 之间查找一条最短路径的话，我们可以在第9行添加条件如果满足 u = t 的话终止程序。

通过推导可知，为了记录最佳路径的轨迹，我们只需记录该路径上每个点的前趋，即可通过迭代来回溯出 s 到 t 的最短路径（当然，使用后继节点来存储亦可。但那需要修改代码）：

现在序列 S 就是从 s 到 t 的最短路径的顶点集。

时间复杂度

我们可以用大O符号将该算法的运行时间表示为边数 m {\displaystyle m} 和顶点数 n {\displaystyle n} 的函数。

对于基于顶点集 Q {\displaystyle Q} 的实现，算法的运行时间是 O ( | E | ⋅ ⋅ --> d k Q + | V | ⋅ ⋅ --> e m Q ) {\displaystyle O(|E|\cdot dk_{Q}+|V|\cdot em_{Q})} ，其中 d k Q {\displaystyle dk_{Q}} 和 e m Q {\displaystyle em_{Q}} 分别表示完成键的降序排列时间和从 Q {\displaystyle Q} 中提取最小键值的时间。

Dijkstra算法最简单的实现方法是用一个链表或者数组来存储所有顶点的集合 Q {\displaystyle Q} ，所以搜索 Q {\displaystyle Q} 中最小元素的运算（Extract-Min( Q {\displaystyle Q} )）只需要线性搜索 Q {\displaystyle Q} 中的所有元素。这样的话算法的运行时间是 O ( n 2 ) {\displaystyle O(n^{2})} 。

对于边数少于 n 2 {\displaystyle n^{2}} 的稀疏图来说，我们可以用邻接表来更有效的实现该算法。同时需要将一个二叉堆或者斐波纳契堆用作优先队列来查找最小的顶点（Extract-Min）。当用到二叉堆的时候，算法所需的时间为 O ( ( m + n ) l o g n ) {\displaystyle O((m+n)logn)} ，斐波纳契堆能稍微提高一些性能，让算法运行时间达到 O ( m + n l o g n ) {\displaystyle O(m+nlogn)} 。然而，使用斐波纳契堆进行编程，常常会由于算法常数过大而导致速度没有显著提高。

相关问题及算法

开放最短路径优先算法是该算法在网络路由中的一个具体实现。

与 Dijkstra 算法不同，Bellman-Ford算法可用于具有负花费边的图，只要图中不存在总花费为负值且从源点 s 可达的环路（如果有这样的环路，则最短路径不存在，因为沿环路循环多次即可无限制的降低总花费）。在可能有环路的情况下，Bellman-Ford算法则可以通过检测程序while循环次数是否大于|V|来进行判断。

与最短路径问题相关最有名的一个问题是旅行商问题，此类问题要求找出恰好通过所有目标点一次且最终回到原点的最短路径。然而该问题为-完全的；换言之，与最短路径问题不同，旅行商问题不太可能具有多项式时间解法。

如果有已知信息可用来估计某一点到目标点的距离，则可改用A*搜索算法，以减小最短路径的搜索范围。

参考

E. W. Dijkstra: A note on two problems in connexion with graphs . In: Numerische Mathematik . 1 (1959), S. 269–271

Thomas 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.

免责声明：以上内容版权归原作者所有，如有侵犯您的原创版权请告知，我们将尽快删除相关内容。感谢每一位辛勤著写的作者，感谢每一位的分享。