Dijkstra 算法
信息安全公益宣传，信息安全知识启蒙。
加微信群回复公众号：微信群；QQ群：16004488
一、Dijkstra 算法的介绍
Dijkstra 算法，又叫迪科斯彻算法（Dijkstra），算法解决的是有向图中单个源点到其他顶点的最短路径问题。举例来说，如果图中的顶点表示城市，而边上的权重表示著城市间开车行经的距离，Dijkstra 算法可以用来找到两个城市之间的最短路径。
二、图文解析 Dijkstra 算法
ok，经过上文有点繁杂的信息，你还并不对此算法了如指掌，清晰透彻。没关系，咱们来幅图，就好了。请允许我再对此算法的概念阐述下，
Dijkstra算法是典型最短路径算法，用于计算一个节点到其他所有节点的最短路径。不过，针对的是非负值权边。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。[Dijkstra算法能得出最短路径的最优解，但由于它遍历计算的节点很多，所以效率低。]
ok，如下图，设A为源点，求A到其他各所有一一顶点（B、C、D、E、F）的最短路径。线上所标注为相邻线段之间的距离，即权值。
（注：此图为随意所画，其相邻顶点间的距离与图中的目视长度不能一一对等）
Dijkstra无向图
算法执行步骤如下表：
三、Dijkstra 的算法实现
Dijkstra 算法的输入包含了一个有权重的有向图 G，以及G中的一个来源顶点 S。我们以 V 表示 G 中所有顶点的集合，以 E 表示G 中所有边的集合。
(u, v) 表示从顶点 u 到 v 有路径相连，而边的权重则由权重函数 w: E → [0, ∞] 定义。因此，w(u, v) 就是从顶点 u 到顶点 v 的非负花费值（cost），边的花费可以想像成两个顶点之间的距离。
任两点间路径的花费值，就是该路径上所有边的花费值总和。
已知有 V 中有顶点 s 及 t，Dijkstra 算法可以找到 s 到 t 的最低花费路径(例如，最短路径)。这个算法也可以在一个图中，找到从一个顶点 s 到任何其他顶点的最短路径。
好，咱们来看下此算法的具体实现：
Dijkstra 算法的实现一（维基百科）：
u := Extract_Min(Q) 在顶点集合 Q 中搜索有最小的 d[u] 值的顶点 u。这个顶点被从集合 Q 中删除并返回给用户。
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
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 := S union {u}
11 for each edge (u,v) outgoing from u
12 if d[v] > d[u] + 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]
现在序列 S 就是从 s 到 t 的最短路径的顶点集。
Dijkstra 算法的实现二（算法导论）：
DIJKSTRA(G, w, s)
1 INITIALIZE-SINGLE-SOURCE(G, s)
2 S ← Ø
3 Q ← V[G] //V*O（1）
4 while Q ≠ Ø
5 do u ← EXTRACT-MIN(Q) //EXTRACT-MIN，V*O（V），V*O（lgV）
6 S ← S ∪{u}
7 for each vertex v ∈ Adj[u]
8 do RELAX(u, v, w) //松弛技术，E*O（1），E*O（lgV）
因为Dijkstra算法总是在V-S中选择“最轻”或“最近”的顶点插入到集合S中，所以我们说它使用了贪心策略。
四、Dijkstra 算法的执行速度
我们可以用大O符号将Dijkstra 算法的运行时间表示为边数 m 和顶点数 n 的函数。Dijkstra 算法最简单的实现方法是用一个链表或者数组来存储所有顶点的集合 Q，所以搜索 Q 中最小元素的运算（Extract-Min(Q)）只需要线性搜索 Q 中的所有元素。这样的话算法的运行时间是 O(E^2)。
对于边数少于 E^2 的稀疏图来说，我们可以用邻接表来更有效的实现迪科斯彻算法。同时需要将一个二叉堆或者斐波纳契堆用作优先队列来寻找最小的顶点（Extract-Min）。
当用到二叉堆时候，算法所需的时间为O(( V+E )logE)，斐波纳契堆能稍微提高一些性能，让算法运行时间达到O(V+ElogE)。(此处一月十六日修正。)
开放最短路径优先（OSPF， Open Shortest Path First）算法是迪科斯彻算法在网络路由中的一个具体实现。
与 Dijkstra 算法不同，Bellman-Ford算法可用于具有负数权值边的图，只要图中不存在总花费为负值且从源点 s 可达的环路即可用此算法（如果有这样的环路，则最短路径不存在，因为沿环路循环多次即可无限制的降低总花费）。
与最短路径问题相关最有名的一个问题是旅行商问题（Traveling salesman problem），此类问题要求找出恰好通过所有标点一次且最终回到原点的最短路径。
然而该问题为NP-hard的；换言之，与最短路径问题不同，旅行商问题不太可能具有多项式时间解法。如果有已知信息可用来估计某一点到目标点的距离，则可改用A*搜寻算法，以减小最短路径的搜索范围。
BFS、DFS、Kruskal、Prim、Dijkstra算法时间复杂度的比较：
一般说来，我们知道，BFS，DFS算法的时间复杂度为O（V+E），最小生成树算法Kruskal、Prim算法的时间复杂度为O（E*lgV）。
而Prim算法若采用斐波那契堆实现的话，算法时间复杂度为O（E+V*lgV），当|V|<<|E|时，E+V*lgV是一个较大的改进。
//|V|<<|E|，=>O（E+V*lgV） << O（E*lgV），对吧。
Dijkstra 算法，斐波纳契堆用作优先队列时，算法时间复杂度为O（V*lgV + E）。
//看到了吧，与Prim算法采用斐波那契堆实现时，的算法时间复杂度是一样的。
所以我们，说，BFS、Prime、Dijkstra 算法是有相似之处的，单从各算法的时间复杂度比较看，就可窥之一二。
五、单源最短路径问题
我们知道，单源最短路径问题：已知图G=(V，E)，要求找出从某个定源顶点s<-V，到每个v<-V的最短路径。
简单来说，就是一个图G中，找到一个定点s，然后以s为起点，要求找出s到图G中其余各个点的最短距离或路径。
此单源最短路径问题有以下几个变形：
单终点最短路径问题
每个顶点v到指定终点t的最短路径问题。即单源最短路径问题的相对问题。
单对顶点最短路径问题
给定顶点u和v，找出从u到v的一条最短路径。
每对顶点间最短路径问题
针对任意每俩个顶点u和v，找出从u到v的最短路径。
最简单的想法是，将每个顶点作为源点，运行一次单源算法即可以解决这个问题。
当然，还有更好的办法，日后在本BOlG内阐述。
六、Bellman-Ford 算法
1、回路问题
一条最短路径不能包含负权回路，也不能包含正权回路。
一些最短路径的算法，如Dijkstra 算法，要求图中所有的边的权值都是非负的，如在公路地图上，找一条从定点s到目的顶点v的最短路径问题。
2、Bellman-Ford 算法
而Bellman-Ford 算法，则允许输入图中存在负权边，只要不存在从源点可达的负权回路，即可。
简单的说，图中可以存在负权边，但此条负权边，构不成负权回路，不影响回路的形成。
且，Bellman-Ford 算法本身，便是可判断图中是否存在从源点可达的负权回路，若存在负权回路，算法返回FALSE,若不存在，返回TRUE。
Bellman-Ford 算法的具体描述
BELLMAN-FORD(G, w, s)
1 INITIALIZE-SINGLE-SOURCE(G, s) //对每个顶点初始化 ，O(V)
2 for i ← 1 to |V[G]| - 1
3 do for each edge (u, v) ∈ E[G]
4 do RELAX(u, v, w) //针对每个顶点(V-1个)，都运用松弛技术O(E)，计为O（(v-1)*E)）
5 for each edge (u, v) ∈ E[G]
6 do if d[v] > d[u] + w(u, v)
7 then return FALSE //检测图中每条边，判断是否包含负权回路，
//若d[v]>d[u]+w(u，v)，则表示包含，返回FALSE，
8 return TRUE //不包含负权回路，返回TRUE
Bellman-Ford 算法的时间复杂度，由上可得为O（V*E）。
3、关于判断图中是否包含负权回路的问题
根据定理，我们假定，u是v的父辈，或父母，那么当G(V,E)是一个有向图或无向图(且不包含任何负权回路)，s<-V，s为G的任意一个顶点，则对任意边(u，v)<-V，有
d[s，v] <= d[s，u]+1
此定理的详细证明，可参考算法导论一书上，第22章中引理22.1的证明。
或者根据第24章中通过三角不等式论证Bellman-Ford算法的正确性，也可得出上述定理的变形。
即假设图G中不包含负权回路，可证得
d[v]=$(s，v)
<=$(s，u)+w(u，v) //根据三角不等式
=d[u]+w[u，v]
所以，在不包含负权回路的图中，是可以得出d[v]<=d[u]+w(u，v)。
于是，就不难理解，在上述Bellman-Ford 算法中，
if d[v] > d[u]+w(u，v)，=> 包含负权回路，返回FASLE
else if =>不包含负权回路，返回TRUE。
ok，咱们，接下来，立马切入Dijkstra 算法。
七、深入浅出，彻底解剖Dijkstra 算法
I、松弛技术RELAX的介绍
Dijkstra 算法使用了松弛技术，对每个顶点v<-V，都设置一个属性d[v]，用来描述从源点s到v的最短路径上权值的上界，称为最短路径的估计。
首先，得用O（V）的时间，来对最短路径的估计，和对前驱进行初始化工作。
NITIALIZE-SINGLE-SOURCE(G, s)
1 for each vertex v ∈ V[G]
2 do d[v] ← ∞
3 π[v] ← NIL //O（V）
4 d[s] 0
RELAX(u, v, w)
1 if d[v] > d[u] + w(u, v)
2 then d[v] ← d[u] + w(u, v)
3 π[v] ← u //O（E）
II、Dijkstra 算法
此Dijkstra 算法分三个步骤
INSERT (第3行)
EXTRACT-MIN (第5行)
DECREASE-KEY(第8行的RELAX，调用此减小关键字的操作)。
DIJKSTRA(G, w, s)
1 INITIALIZE-SINGLE-SOURCE(G, s) //对每个顶点初始化 ，O(V)
2 S ← Ø
3 Q ← V[G] //INSERT，O(1)
4 while Q ≠ Ø
5 do u ← EXTRACT-MIN(Q) //简单的O(V*V)；二叉/项堆，和FIB-HEAP的话，则都为O(V*lgV)。
6 S ← S ∪{u}
7 for each vertex v ∈ Adj[u]
8 do RELAX(u, v, w) //简单方式:O(E)，二叉/项堆，E*O(lgV)，FIB-HEAP，E*O(1)。
八、Dijkstra 算法的运行时间
在继续阐述之前，得先声明一个问题，DIJKSTRA（G，w，s）算法中的第5行，EXTRACT-MIN(Q)，最小优先队列的具体实现。
而Dijkstra 算法的运行时间，则与此最小优先队列的采取何种具体实现，有关。
最小优先队列三种实现方法：
利用从1至|V| 编好号的顶点，简单地将每一个d[v]存入一个数组中对应的第v项，如上述DIJKSTRA（G，w，s）所示，Dijkstra 算法的运行时间为O(V^2+E)。
如果是二叉/项堆实现最小优先队列的话，EXTRACT-MIN(Q)的运行时间为O(V*lgV)，所以，Dijkstra 算法的运行时间为O(V*lgV+E*lgV)，若所有顶点都是从源点可达的话，O（(V+E)*lgV）=O（E*lgV）。当是稀疏图时，则E=O(V^2/lgV)，此Dijkstra 算法的运行时间为O(V^2)。
采用斐波那契堆实现最小优先队列的话，EXTRACT-MIN(Q)的运行时间为O(V*lgV)，所以，此Dijkstra 算法的运行时间即为O(V*lgV+E)。
综上所述，此最小优先队列的三种实现方法比较如下：
EXTRACT-MIN + RELAX
I、 简单方式： O（V*V + E*1）
II、 二叉/项堆： O（V*lgV + |E|*lgV）
源点可达：O（E*lgV）
稀疏图时，有E=o（V^2/lgV），
=> O（V^2）
III、斐波那契堆：O（V*lgV + E）
当|V|<<|E|时，采用DIJKSTRA（G，w，s）+ FIB-HEAP-EXTRACT-MIN(Q)，即斐波那契堆实现最小优先队列的话，优势就体现出来了。
九、Dijkstra 算法 + FIB-HEAP-EXTRACT-MIN(H)，斐波那契堆实现最小优先队列
由以上内容，我们已经知道，用斐波那契堆来实现最小优先队列，可以将运行时间提升到O（VlgV+E）。|V|个EXTRACT-MIN 操作，每个平摊代价为O（lgV），|E|个DECREASE-KEY操作的每个平摊时间为O（1）。
下面，重点阐述DIJKSTRA(G, w, s)中，斐波那契堆实现最小优先队列的操作。
由上，我们已经知道，DIJKSTRA算法包含以下的三个步骤：
INSERT (第3行)
EXTRACT-MIN (第5行)
DECREASE-KEY(第8行的RELAX)
先直接给出Dijkstra 算法 + FIB-HEAP-EXTRACT-MIN(H)的算法：
DIJKSTRA(G, w, s)
1 INITIALIZE-SINGLE-SOURCE(G, s)
2 S ← Ø
3 Q ← V[G] //第3行，INSERT操作，O（1）
4 while Q ≠ Ø
5 do u ← EXTRACT-MIN(Q) //第5行，EXTRACT-MIN操作，V*lgV
6 S ← S ∪{u}
7 for each vertex v ∈ Adj[u]
8 do RELAX(u, v, w) //第8行，RELAX操作，E*O(1)
FIB-HEAP-EXTRACT-MIN(H) //平摊代价为O（lgV）
1 z ← min[H]
2 if z ≠ NIL
3 then for each child x of z
4 do add x to the root list of H
5 p[x] ← NIL
6 remove z from the root list of H
7 if z = right[z]
8 then min[H] ← NIL
9 else min[H] ← right[z]
10 CONSOLIDATE(H)
11 n[H] ← n[H] - 1
12 return z
十、Dijkstra 算法 +fibonacci堆各项步骤的具体分析
ok，接下来，具体分步骤阐述以上各个操作：
第3行的INSERT操作：
FIB-HEAP-INSERT(H, x) //平摊代价，O（1）.
1 degree[x] ← 0
2 p[x] ← NIL
3 child[x] ← NIL
4 left[x] ← x
5 right[x] ← x
6 mark[x] ← FALSE
7 concatenate the root list containing x with root list H
8 if min[H] = NIL or key[x] < key[min[H]]
9 then min[H] ← x
10 n[H] ← n[H] + 1
第5行的EXTRACT-MIN操作：
FIB-HEAP-EXTRACT-MIN(H) //平摊代价为O（lgV）
1 z ← min[H]
2 if z ≠ NIL
3 then for each child x of z
4 do add x to the root list of H
5 p[x] ← NIL
6 remove z from the root list of H
7 if z = right[z]
8 then min[H] ← NIL
9 else min[H] ← right[z]
10 CONSOLIDATE(H) //CONSOLIDATE算法在下面，给出。
11 n[H] ← n[H] - 1
12 return z
下图是FIB-HEAP-EXTRACT-MIN 的过程示意图：
CONSOLIDATE(H)
1 for i ← 0 to D(n[H])
2 do A[i] ← NIL
3 for each node w in the root list of H
4 do x ← w
5 d ← degree[x] //子女数
6 while A[d] ≠ NIL
7 do y ← A[d]
8 if key[x] > key[y]
9 then exchange x <-> y
10 FIB-HEAP-LINK(H, y, x) //下面给出。
11 A[d] ← NIL
12 d ← d + 1
13 A[d] ← x
14 min[H] ← NIL
15 for i ← 0 to D(n[H])
16 do if A[i] ≠ NIL
17 then add A[i] to the root list of H
18 if min[H] = NIL or key[A[i]] < key[min[H]]
19 then min[H] ← A[i]
FIB-HEAP-LINK(H, y, x) //y链接至 x。
1 remove y from the root list of H
2 make y a child of x, incrementing degree[x]
3 mark[y] ← FALSE
第8行的RELAX的操作，以上已经给出:
RELAX(u, v, w)
1 if d[v] > d[u] + w(u, v)
2 then d[v] ← d[u] + w(u, v)
3 π[v] ← u //O（E）
一般来说，在Dijkstra 算法中，DECREASE-KEY的调用次数远多于EXTRACT-MIN的调用，所以在不增加EXTRACT-MIN 操作的平摊时间前提下，尽量减小DECREASE-KEY操作的平摊时间，都能获得对比二叉堆更快的实现。
以下，是二叉堆，二项堆，斐波那契堆的各项操作的时间复杂度的比较：
操作 二叉堆(最坏) 二项堆(最坏) 斐波那契堆(平摊)
_________________________________
MAKE-HEAP Θ(1) Θ(1) Θ(1)
INSERT Θ(lg n) O(lg n) Θ(1)
MINIMUM Θ(1) O(lg n) Θ(1)
EXTRACT-MIN Θ(lg n) Θ(lg n) O(lg n)
UNION Θ(n) O(lg n) Θ(1)
DECREASE-KEY Θ(lg n) Θ(lg n) Θ(1)
DELETE Θ(lg n) Θ(lg n) O(lg n)
▼ 点击阅读原文，查看更多精彩文章。