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