Dijkstra(迪杰斯特拉算法)

假设有如下一个图

我们要做的是找到点a到点g的最小距离,并且点与点之间会有权值,这时候我们可以使用迪杰斯特拉算法
使用这个算法,路径是这样的.
首先先把上图转化成邻接矩阵.

  • 初始化一个关闭列表数组,代表已经寻找过的,(防止回溯), 里面放入开始节点,因为第一个寻找的就是开始节点
  • 需要一个开放列表数组,存储所有已经找过的最短路径,里面初始化好a到各点的距离(INF是无效大,代表这个点无法到达,也可以用一个很大权值代表)

  • 循环邻接矩阵的第一行,拿到开放列表中最小值1,索引为b`,并把这个索引标记到关闭列表.
  • 得到上一行最小值的索引,取邻接矩阵的这一行数据,就是第b行的数据.
  • 然后这一行的每一个数据加上取得的最小值,看是否小于开放列表的数据.(如,第b行的aINF + 最小值1并不小于开放列表的a => INF)(如,第b行的d1 + 最小值1等于2小于开放列表的d => INF,则这时候把开放列表中的d从原来的INF改为2)经过此次循环,数据将变成这样子.

  • 重复上一个步骤
  • 循环邻接矩阵的第一行,拿到开放列表中最小值2,索引为c(因为b`已经被标记在关闭列表了),并把这个索引标记到关闭列表.
  • 得到上一行最小值的索引,取邻接矩阵的这一行数据,就是第c行的数据.
  • 然后这一行的每一个数据加上取得的最小值,看是否小于开放列表的数据.(第c行只有一个f => 2 加上最小值2等于4小于开放列表中的f => INF)经过此次循环,数据将变成这样子.

  • 重复上一个步骤
  • 循环邻接矩阵的第一行,拿到开放列表中最小值2,索引为d(因为bc`已经被标记在关闭列表了),并把这个索引标记到关闭列表.
  • 得到上一行最小值的索引,取邻接矩阵的这一行数据,就是第d行的数据.
  • 然后这一行的每一个数据加上取得的最小值,看是否小于开放列表的数据.(第df => 4 加上最小值2等于6并不小于开放列表中的f => 4,所以舍弃这跳路径)经过此次循环,数据将变成这样子.

  • 以此类推,直至循环结束后,开放列表里存储的是任意一个点到a的最短权值距离.

实现代码如下:


点赞

发表评论

电子邮件地址不会被公开。 必填项已用*标注