0.算法属性
类别：查找算法
数据结构：图
性能：O(|E|+|V|log|V|)
1.算法介绍
Dijkstra算法是求图中两节点间最短路径的一种算法。它可以表示：例如，道路网络。
它的构思是由计算机科学家Edsger W. Dijkstra在1956想出并在三年后提出的。
这个算法存在许多版本；Dijkstra的最初版本是求两结点之间的最短路径，但更常见的版本是将单一节点作为“源”节点，去计算从源头到图中的所有其他节点的最短路径，并生成树。
最短路径的算法被广泛应用于网络的路由协议，比如最著名的是OSPF(优先开放最短路径)。也被用作子算法，如Johnson’s algorithm
Dijkstra原始算法并没有使用最小优先队列，运行时间为O(|V|^2)(其中|V|表示节点的数量)。
这种算法思想在1957年被Leyzorek等人提出。在1984年被Fredman和Tarjan实现在斐波那契堆中，
并且运行时间为O(|E|+|V|\log|V|)(其中 |E|为边的数量)
这是在任意有向图和无界非负权重的情况下，一个以渐进的方式最快的算出已知单源最短路径算法。
2.算法示意图
示意一：
计算a到b的距离。其中：
1.两点间的实际距离为连接线上的数字。
2.节点圆圈中的数字为该节点的标示符。
3.节点边上蓝色数字为起始节点a到该节点的最小距离。
4.若计算出的距离值比当前所标示的距离值小，则更新反之不更新。节点初始值为无限大。
5.访问过的节点标示为红色，下一次忽略该节点(即该节点的最小距离值不再改变,状态为out)。
计算结果：
a到节点1的最小距离为：0
a到节点2的最小距离为: 7
a到节点3的最小距离为: 9
a到节点6的最小距离为：11
a到节点5的最小距离为: 20
示意二：
从开始节点(左下角的红色节点)到目标节点(右上角的绿色节点)的查找示意图。其中空心节点表示“暂定”集，填充节点表示”被访问”过的。颜色代表距离，颜色越绿代表距离越远。不同方向上的节点是均匀分布的，Dijkstra算法使用了一个启发式恒等于0，像波浪一样渐进发现节点。
示意三：
从左到右，从上到下：
图一：以左上角的点为起始节点，计算到图中所有其它节点的最小距离。初始值为99(一个很大的值)，起始节点初始值为0，各相邻节点的实际距离为边线上的值。
图二：以“起始节点”为“当前节点”，计算出到各相邻节点的最小距离，由于各相邻节点的初始值为99，比实际距离要大，所以更新各自的值，依次为2,6,9.
图三：在2、6、9中最小的是2，所以将2作为“当前节点”，更新2的相邻节点为3(2+1=3),5(2+3=5<6).注意发现过的节点不能再计算，并且要遵守图的有向性。
图四：在3、5中最小的是3，所以将3当做“当前节点”，更新3的相邻节点为4(3+1=4<5),9(3+6=9).
图五：在4、9中最小的为4，所以将4当做“当前节点”，更新4的相邻节点为13(4+9=13),11(4+7=11),6(4+2=6<9).
图六：在13,11,6中最小的为6，所以将6当做“当前节点”，更新6的相邻节点为10(6+4=10<11).
图七：只有10这条路，所以更新10相邻的节点为11(10+1)
图八：….
图九：….
3.算法思路
让我们把开始的节点称为“起始节点”，从“起始节点”到节点Y的距离标记为Y。Dijkstra算法事先分配一些初始的距离值，并在后面逐步提高他们。
1.分配给每个节点一个暂定的距离值，设置起始节点值为0，其余节点值为无限大。
2.设置起始节点为当前(current)。标记其它所有节点为未发现(unvisited)。创建一个数据集合(包含所有未发现的节点),称作未发现数据集(unvisited set).
3.对于当前的节点，考虑所有未访问过的邻居并计算出他们“暂时距离”。比较新计算出的“暂时距离”和当前分配的值，并分配较小的一个。例如，如果当前节点A被标记距离值为6，A距离邻居节点B的长度为2，计算出一个临时值(通过A)为6+2=8.如果B事先标记的值大于8，则将其改为8。否则，保持当前值。
4.当我们考虑完所有当前节点的邻居节点后，标记当前节点为已发现节点(visited node)并且把它从未发现数据集(unvisited set)中移除。已发现节点(visited node)永远不会被再次检查。
5.如果目标节点被标记为已发现(当规划两个节点之间的路径时)或者如果这个最小距离在未发现节点集合中被计算为无限大(当计划一个完整的遍历，发现没有一个连接从起始节点到剩余未访问的节点)，然后就停止，这个算法就结束了。
6.否则，选择一个未访问过的节点(被标记为最小临时距离的)作为新的“当前节点”，然后回到步骤3重复执行。
4.伪代码
1 function Dijkstra(Graph,source):
2
3 dist[source] ← 0 //从起始节点到起始节点的距离
4 prev[source] ← undefined //最优路径初始化中的前一个节点
5
6 create vertex set Q //创建节点集
7
8 for each vertex v in Graph: //初始化
9 if v ≠ source: //v 还没从Q中移除(未发现的节点)
10 dist[v] ← INFINITY //不知道从source到v的距离
11 prev[v] ← UNDEFINED //上一个到source最佳路径的节点
12 add v to Q //Q中所有初始的节点(未发现的节点)
13
14 while Q is not empty:
15 u ← vertex in Q with min dist[u] //第一种情况下的源节点
16 remove u from Q
17
18 for each neighbor v of u: //v还在Q中
19 alt ← dist[u] + length(u,v)
20 if alt < dist[v]: //到V的最短路径被发现
21 dist[v] ← alt
22 prev[v] ← u
23
24 return dist[],prev[]
如果我们只是计算从源节点到目标节点的最短路径，我们可以在第16行后终止搜索，如果u = target。现在我们可以通过反向迭代的方式读取从源到目标的最短路径：
1 S ← empty sequence
2 u ← target
3 while prev[u] is defined: // 用栈S构建最短路径
4 insert u at the beginning of S // 将顶点推到堆栈上
5 u ← prev[u] // 从目标转向源节点
使用优先队列：
最小优先队列是一个抽象数据类型，它提供了3个基本操作：add_with_priority()，decrease_priority()和extract_min()。如前所述，使用这样的数据结构可以比使用一个基本队列产生更快的计算时间。值得注意的是，斐波那契堆（Fredman和Tarjan 1984提出的）或Brodal队列提供了这3个操作的最佳实现。由于算法是有点不同的，我们在这里提到了，它的伪代码：
1 function Dijkstra(Graph, source):
2 dist[source] ← 0 // 初始化
3
4 create vertex set Q
5
6 for each vertex v in Graph:
7 if v ≠ source
8 dist[v] ← INFINITY // 不知道从源节点到V的距离
9 prev[v] ← UNDEFINED // v的前一个节点
10
11 Q.add_with_priority(v, dist[v])
12
13
14 while Q is not empty: // 主循环
15 u ← Q.extract_min() // 删除并返回最佳顶点
16 for each neighbor v of u: // 只有v仍然在Q中
17 alt = dist[u] + length(u, v)
18 if alt < dist[v]
19 dist[v] ← alt
20 prev[v] ← u
21 Q.decrease_priority(v, alt)
22
23 return dist[], prev[]
不是在初始化时将所有节点都填充到优先级队列中，也可以在初始化时只包含源节点，当alt < dist[v]时，并且没有在队列中，那么这个节点必须被插入。
5.代码实现
java版：