如果发现广告等破坏行为，请尽量将条目恢复到较早的版本而不是把相应内容直接删除，谢谢合作。

来自"NOCOW"

 这篇文章可以证实是由NOCOW用户原创，不存在任何版权争议。
 本文作者同意以GNU FDL、CC-by-sa和GNU LGPL（如果适用）三种版权发布此文章（不包括翻译文章中属于原始所有者的部分版权）。
 如果你修改了这篇文章并且不同意用GNU FDL以外的版权发布，可以换一个版权模板或者移除此模板。

Dijkstra算法是一种求单源最短路的算法，即从一个点开始到所有其他点的最短路。其基本原理是：每次新扩展一个距离最短的点，更新与其相邻的点的距离。当所有边权都为正时，由于不会存在一个距离更短的没扩展过的点，所以这个点的距离永远不会再被改变，因而保证了算法的正确性。不过根据这个原理，用Dijkstra求最短路的图不能有负权边，因为扩展到负权边的时候会产生更短的距离，有可能就破坏了已经更新的点距离不会改变的性质。

如果用本算法求一个图中全部的最短路，则要以每个点为源调用一次Dijkstra算法。

目录 1 适用条件与限制 2 算法流程 3 算法实现 3.1 直接实现 3.2 二叉堆实现 3.3 菲波那契堆实现 4 程序 5 扩展 5.1 第k短路 6 练习

[编辑] 适用条件与限制

• 有向图和无向图都可以使用本算法，无向图中的每条边可以看成相反的两条边。
• 用来求最短路的图中不能存在负权边。(可以利用拓扑排序检测)

[编辑] 算法流程

在以下说明中，s为源，w[u,v]为点u和v之间的边的长度，结果保存在dist[]

1. 初始化：源的距离dist[s]设为0，其他的点距离设为无穷大，同时把所有的点的状态设为没有扩展过。
2. 循环n-1次：
   1. 在没有扩展过的点中取一距离最小的点u，并将其状态设为已扩展。
   2. 对于每个与u相邻的点v，执行Relax(u,v)，也就是说，如果dist[u]+w[u,v]<dist[v]，那么把dist[v]更新成更短的距离dist[u]+w[u,v]。此时到点v的最短路径上，前一个节点即为u。
3. 结束。此时对于任意的u，dist[u]就是s到u的距离。

[编辑] 算法实现

[编辑] 直接实现

最简单的实现方法就是，在每次循环中，再用一个循环找距离最短的点，然后用任意的方法更新与其相邻的边，时间复杂度显然为O(n²)

对于空间复杂度：如果只要求出距离，只要n的附加空间保存距离就可以了（距离小于当前距离的是已访问的节点，对于距离相等的情况可以比较编号或是特殊处理一下）。如果要求出路径则需要另外V的空间保存前一个节点，总共需要2n的空间。

[编辑] 二叉堆实现

使用二叉堆(Binary Heap)来保存没有扩展过的点的距离并维护其最小值，并在访问每条边的时候更新，可以把时间复杂度变成O(n+mlogn)。

当边数远小于点数的平方时，这种算法相对来说有很好的效果。但是当m=O(n²)时（有时候表现为不限制边的条数），用二叉堆的优化反倒会更慢。因为此时的复杂度是O(n+n²logn)，大于不用堆的实现的O(n²)的复杂度。

另外此时要用邻接表保存边，使得扩展边的总复杂度为O(m)，否则复杂度不会减小。

空间复杂度：这种算法需要一个二叉堆，及其反向指针，另外还要保存距离，所以所用空间为3n。如果保存路径则为4n。

具体思路：先将所有的点插入堆，并将值赋为极大值(maxint/maxlongint)，将原点赋值为0，通过松弛技术（relax）进行更新以及设定为扩展。

[编辑] 菲波那契堆实现

• 用类似的方法，使用Fibonacci Heap可以将复杂度降到O(m+nlogn)，但实现比较麻烦。因此不宜在时间较短的信息学竞赛中使用。详见Fibonacci堆。

[编辑] 程序

二叉堆实现_Pascal

二叉堆实现_C

二叉堆实现_C++

[编辑] 扩展

[编辑] 第k短路

当k比较小时，可以直接在每个点保存k条最短路。更新的时候对每条能更新的路都更新一遍。此时每次更新的代价相当于把两个长度为k的表合并在一起，所以复杂度为纯Dijkstra实现的复杂度×O(k)。

曹氏短边法：每次将任意一条边赋值为MAX，重复计算数次后得到k短路径。

[编辑] 练习

Sweet Butter(USACO 3.2.6)