Dijksta 算法用于求单源最短路径长度，所谓单源最短路径长度就是，在一个图中求一个顶点到其他所有顶点的最短路径长度。适用于带权值的图，不能用于带负权值的图。
算法思想
- 1.初始化阶段
- 首先需要确定一个源节点（假设为 s ）。将所有节点分为两个集合，一个集合是已经确定了的最短路径的节点集合（设为 S ），初始时 S = {s}，因为源节点到自身的最短路径长度为 0 .另一个集合是还未确定最短路径的集合（设为V-S），其中 V 是图中所有节点的集合。
- 同时，为每个节点 v 维护一个距离值 d[v] ，初始时 d[s] = 0,对于其他节点 v ∈ V-S ，d[v] 的值设为无穷大（在实际计算中，可以用一个很大的值来表示，表示当前还未找到能够通往该节点的路径）。这个距离值 d[v] 表示从源节点 s 到节点 v 的当前最短路径长度的估计值。
- 2.迭代阶段
- 在每次迭代中，从集合 V-S 选择一个距离值最小的节点 u ,即 u = arg min d[v] (其中v∈V-S)，arg 表示找到距离值最小的节点 v ,然后将这个最小的节点 u 加入到集合 S 中。
- 然后，对于与节点 u 相邻的所有节点 v (即存在边（u,v）)，检查是否可以通过节点 u 来更新节点 v 的最短路径长度。更新的规则是：如果 d[u] + w(u,v) < d[v] ，则 d[v] = d[u] + w(u,v)，其中 w(u,v)是边（u,v）的权重。（把更新最短路径这一步骤称为“松弛操作”）
- 3.终止条件
- 重复上述迭代过程，直到集合 V-S 为空，即所有节点都已经加入到集合 S 中。此时，每个节点的距离值 d[v] 就是从源节点 s 到节点 v 的最短路径长度。
用一个简单的比喻来理解 Dijkstra 算法：想象你在一个陌生的城市（图）中，从一个特定的地点（源节点）出发，要找到去其他各个地点的最短路线。一开始，你只知道从出发地到自己的距离是，其他地方看起来都很远（距离设为无穷大）。然后，你每次找到离你当前 “已知最短路径范围” 最近的一个新地点，把它纳入你的 “已探索范围”（加入集合），并且看看通过这个新地点，是否能找到去其他还没探索地点的更短路径。不断重复这个过程，直到你探索完整个城市
Dijkstra 算法例子
例子参考自 Dijkstra 算法
初始化
初始：假设从 V0 开始，需要初始化三个数组信息
final 用来标记各顶点是否已找到最短路径，用布尔变量来表示。
dist 表示最短路径的长度。从有向图中可以看出，从 V0 开始，则dist[0] 为0，V[0] 连接 V[1] 和 V[4] ，则先把 V[1] 和 V[4] 设为相应的权值。
path 记录路径上的前驱，表示各个节点的前驱节点，算法结束后可以通过这个数组找到相应最短路径。初始时，从 V0 开始，知道 V[1] 和 V[4] 的前驱是 V[0] ，则让 V[1] = 0，V[4] = 0
第一轮处理
- 循环遍历所有节点，找到还没确定最短路径，且 dist 最小的顶点 Vi ，令 final[i] = true
可以找到当前 dist 值最小的顶点是 V4 ，将 final[4] = true
- 检查所有邻接自 Vi 的顶点，若其 final 值为 false ，则更新 dist 和 path 信息
V[4] 连接的节点分别是 V1 , V2 和 V3
首先研究 V1，从 V0 -> V4 -> V1 的路径为 8，显然比 V0 -> V1 的路径更短。根据上述的更新规则，如果 d[u] + w(u,v) < d[v] ,则，d[v] = d[u] + w(u,v)，所以更新 dist[1] 为 8,则相应的 path[1] = 4,表示V1的前驱更改为V4
接着研究 V2，同理，一开始 dist[2] 为无穷，显然满足 d[u] + w(u,v) < d[v],则更新 dist[2] = 5 + 9 = 14,更新path[2] = 4，表示V2的前驱为V4
V3 与 V2 同理，dist[3] = 7,path[3] = 4
第一轮处理结果为：
第二轮处理
第二轮处理与第一轮处理一样，循环遍历所有节点，找到还没确定最短路径，且 dist 最小的顶点 Vi ，令 final[i] = true
找到还没确定最短路径的节点为 V[3] ，将 final[3] = true
和第一轮处理一样，接下来检查 V3 的所有邻接节点，若其对应的 final 为 false，则更新 dist 和 path的信息
V3 的邻接节点为 V0 和 V2
对于 V2来说，显然 dist[3] + 6 = 13 < dist[2] = 14 ，满足更新规则，更新 dist[2] = 13,path[2] = [3]
对于 V0 来说，其 final[0] 为 true，不做处理。
第三轮处理
第三轮处理和前面两轮一样，找到还没确定最短路径，且 dist 最小的节点 Vi，令 V[i] = true
找到还没确定最短路径，且dist为最小的节点为V1，令 v[1] = true
接下来检查所有邻接 V1 的节点，若其 final 值为 false，则更新 dist 和 path 信息
满足条件的是 V2
满足更新规则 d[u] + w(u,v) < d[v],即d[1] + 1 = 9 < 13，更新d[2] = 9，path[2] = 1
第四轮处理
第四轮处理为最后一轮处理
此时只剩下 V2 还未确定最短路径，将 final[2] = true。也无法找到还没确定最短路径，且dist为最小的节点。算法到此结束。
最终得到的数组如下：
使用数组信息
Dijkstra算法是求单源最短路径的算法，也就是一次只能求出某一节点到其他所有节点的最短路径。
由于一开始初始化是从 V0 开始，所以找的是从 V0 开始到其他所有节点的最短路径。首先可以知道dist[2] = 9 ，也就是从 V0 到达 V2 的最短路径是 9，接下来通过path[2] 可以得到 V2 前驱节点的是 V1，通过 path[1] 可以得到 V1 的前驱节点是 V4，通过 path[4] 可以得到V4的前驱节点是V0，所以最短路径是 V2 <- V1 <- V4 <- V0
如果要求其他节点到其他所有节点的最短路径，可以多次使用 Dijkstra 算法，每次指定不同的源节点即可。
Dijkstra 算法时空复杂度
若使用邻接矩阵存储图，时间复杂度为 O（V2）,V 是顶点数量。每次迭代时需要在未确定最短路径的顶点集合中找到距离源顶点距离最近的顶点，这个操作的时间复杂度为 O（V），并且一共需要进行 V-1（或V，取决于第一次初始化） 次这样的迭代，所以总的时间复杂度为 O（V2）
空间复杂度为 O（V）
Dijkstra 算法不能用于带负权值的图
如图所示，如果采用 Dijkstra 算法处理，那么会得到 V0 到 V2 的最短路径为 V0->V2，路径长度为 7 . 实际上最短路径长度为 5 ，路径为 V0 -> V1 ->V2