Dijkstra算法

Dijkstra算法是从一个节点到区域各节点的最短路径算法，解决的是最短路径问题。
特点：以起点为中心，向外层层扩展，直到扩展到终点为止。

我们引入两个集合closelist、openlist和两个集合

• 闭集closelist：记录已求出最短路径的节点。
• 开集openlist：记录还未求出最短路径的节点。
• 集合1：记录源节点到各节点的距离
• 集合2：记录节点对应的父节点

算法操作步骤：

1 首先，将源节点加入集合closelist，其他节点加入到openlist中，计算A到其他节点的距离，源节点无法直接到达的距离记为 ∞ \infty ∞.。
2 从openlist中选出“距离最短的顶点N”，并将顶点N加入到closelist中；同时，从openlist中移除顶点N。
3 重新计算openlist中各个节点到起点A的距离。（重新计算openlist中节点的距离，是由于上一步中确定了N是求出最短路径的顶点，从而可以利用N来更新其他顶点的距离。例如：A到B再到C的距离可能小于A到C的距离，这时应该更改A到C的距离，C的父节点也会改变。）
4 重复上面两个步骤，直到遍历所有的节点。

例子：找A到G的最短路径

1 首先，将源节点A放入闭集合中，并将未求出的节点放入开集合，具体如下：

2 在开集合中选择距离最小的点，显然可以得到此点为B，并将B从开集合删除加入到闭集合中。

3 利用节点B，重新计算所有节点到A的距离（假设此例子中AC<AB+BC，且AC<AB+BF，则C在集合1的距离不变，其父节点也不变，把C从开集中移除加入到闭集，接下去以C遍历其相邻点。）

以此类推直到所有节点都被寻找完，并且闭集合中出现了终点。

最短路径：G==>F==>E==>C==>B==>A