算法笔记：Dijkstra单源最短路算法

噫，好！

---

好看的

算法作用

Dijkstra算法是在正权值的图中，对于某个特定的源节点寻找所有节点到该节点的最短路径的一种算法。

准备工作

要执行Dijkstra算法，需要如下元素：

• 一张没有负权重的带权图G.
• 一个标记数组vis[]，用于标记某个节点是否访问过.
• 一个距离数组dis[]，用于记录某一时刻已知的最短路径.
• 给定的源点S.

算法步骤

首先在距离数组中将源点到自身的距离设为0（显然可得），将源点到其他点的距离设为+INF（意为在当前已知的情况下无法到达）。

1. 选取当前距离数组中 距离源点最短的、且此前没有访问过（vis[P] == 0） 的节点P. 在初始情况下，我们选择的显然是源点S；
   在确定选择以后将vis[P]设为1，意即已经访问过这个点了。
2. 搜索每一条与P所连接的边，记为<P, E, D>（从P通过E连接到D）：若vis[D] == 1，则跳过该条边（D的最短路已经被计算过了）。；
   有如下等式：vis[D] = min(vis[D], vis[P] + w(E))（w(E)为E的边权值）.
   如何理解这一不等式：不停的枚举从源点S出发、通过当前讨论的P点、终点是D的路径，若该路径的长度小于现有记录的路径的长度，则说明现有记录的路径的长度错误，应当更新。
3. 在搜索完P所连接的每一条边、并更新vis数组的值以后，回到1.；当所有点都被访问过的时候，算法终止。

正确性证明

算法正确性证明

关于负权边的说明

由于Dijkstra算法不会重复考虑已经被访问过的点，且该算法在选取顶点的时候优先选择当前距离源点距离最小的点，所以假设以下情况：

A -2-> B A -10-> C C -(-20)->B

在这种情况下，Dijkstra算法会优先选择B点，并且在此之后不再计算B点的最短路（即便存在一条更短的A->C->B的路径）。

TODO：优先队列优化的Dijkstra算法