Dijkstra 算法

求给定非负权边图两个点之间的最短通路

1. 初始化：把起始点标记 P（已经求出最短通路），$d(v_i)$ 是目前从起始点到 $v_i$ 点的最短通路长度，初始化 $d(v_1)=0,d(v_i)=\infty$，把起始点连边加入 d
2. 拓展：找到 d 里面最小的结点，置 P，
3. 修改：修改刚刚最小结点临近的非 P 点的 d 值，修改成目前的最小值（同时可以记录从那个结点连的来记录最短通路），重复 2 直到目标点标记为 P 为止
4. 此时终点的 d 值为最短通路长度（最短通路从后往前找就行了）

dijkstra 的算法思想是从以上最短距离数组中每次选择一个最近的点，将其作为下一个点，然后重新计算从起始点经过该点到其他所有点的距离，更新最短距离数据。已经选取过的点就是确定了最短路径的点，不再参与下一次计算。

转移方程：

$$d(v_i)=\{\begin{array}{ll}d(v_k)+w(v_k,v_i)& ,d(v_k)+w(v_k,v_i)<d(v_i)\\ d(v_i)& ,else\end{array}$$