正文

简单介绍下迪杰斯特拉算法,一般用于寻找最短路.

  • 如图1到6的最短路是: 1 -> 2 -> 3 -> 5 -> 6
  • 注意到在最短路径中,起点到中间节点比如 1 -> 3 的最短路仍然包含在整个最短路径中 1 -> 2 -> 3,这很容易验证,如果起点到中间点有
    更短的路径,那么起点到终点最短路径就不是上面那一条了,显然矛盾.
  • 基于上述思想,我们可以找到一条从起点到终点的路径(最短路径),其起点到每一个中间节点的距离依然是这两者的最短距
    离,于是我们只需要找到离当前节点最近的节点作为当前路径的下一个目的地,直到到达终点或者遍历完所有可到达点为止.

基本流程:

  1. 建立存储矩阵,存放点到点的距离,初值默认无穷大:
  2. 创建最短距离数组,存放起始点到各个点的距离,初值默认无穷大:
  3. 创建标记数组,标记该点是否已访问,初值默认False.
    1. 标记起点.
    2. 从起点开始,访问离起点最近的值(此处为2)并标记,更改最短距离数组中节点2的值.
    3. 找离 2 最近的点(此处为4),访问并标记,更改最短距离数组中节点4的值.
    4. …
    5. 到达终点或遍历完所有可到达节点,结束.

参考文献

🔗Dijkstra算法图文详解🔗