算法 Dijkstra 最短路径算法的理解与实现

yfractal for Beansmile · 发布于 2017年2月02日 · 最后由 yfractal 回复于 2017年2月18日 · 2379 次阅读
7072
本帖已被设为精华帖!

Dijkstra大学的时候就学过,但最近在《Algorithms》这本书里,看到了个很有趣的讲解,对这个算法有了新的理解,以下便是对这个算法的整理和实现。

广度搜索与最短距离

我们知道,如果把所有的边的距离当做1,广度遍历得到的就是最短路径。

更直观的,我们可以这样想,把节点都想成有质量的小球,节点间边想成细线。我们把S球拎起来,让所有的球都自然下垂,这样小球所在的层数,就是S球到其他小球的最短距离了。如下图:

我们可以简单证明下。

首先,广度搜索,又被称为层次遍历,就是一层一层进行搜索。当搜索到d层,所有小于d层的节点一定已经搜索完了。

假设在某一个时刻,所有d层的节点都已经计算正确了。那么他们相邻的节点的距离只有两种情况,一种是未知的,那么他们同S的最短距离应为d + 1。

一种是已知的,距离小于等于d,根据假设,他的距离也已经计算正确了。

然后,我们再考虑初始情况。S节点的距离为0,相邻的节点距离都为1,符合我们的假设。所以通过广度搜索得到的距离是最短距离。

这个"证明"只是用来理解这个算法的,并不去严谨,《算法导论》有严谨的证明,大家感兴趣的话可以去看看。

广度搜索到Dijkstra

既然我们知道广度搜索能得到所有边的距离为1的节点的最短距离了。那么广度搜索和Dijkstra有没有什么关系呢?换句话说,最短路径能不能变成广度搜索呢?

最短路径和广度搜索的区别就在于,广度遍历之间的节点距离只能为1,而最短路径计算的节点距离可以为任意正数。

如果我们把所有距离都变成1会怎样?

为了达到这个目的,我们把两个几点之间加上如果哑节点(dummy node),让所有节点(节点+哑几点)间的距离为1,这样我们就可以用广度遍历来算最短距离了!

比如s同u的距离为3,那么我们可以在S和U之间加上两个节点u1 ,u2。这样就变成了S -> U1 -> U2 -> U,相邻的节点间的距离为1。如下图:

目前的算法看起来有点蠢,不过已经很接近Dijkstra了。我们看下如何来优化它!

优化当前的算法吗

算法好玩的地方就在于,我们可以优化它。

首先,我们先分析这个算法的问题。

假设从S到U的距离是100,那么计算前99个哑节点的距离,都是没有意义的。

如果我们在90分钟里,睡一下,在第一百分钟的时候,有一个闹铃把我们叫醒,就好了!让我们来做这样的一个闹铃!

假设我们要求下图的的最短距离,我们可以这么做。我们从0出发,从图中可以看出来,直到100或者200分钟后,不会有任何有趣的事情发生。那我们就设两个闹铃,分别为100分钟、200分钟之后响。

等到100这个闹铃响的时候,我们到了1号节点,这个时候,我们检查1号节点的相邻节点,发现50分钟后,可能会到2号节点。所以我们加入150这个闹铃。

150分钟到的时候,我们到了2号节点,所以2号的最短距离是150。这样就得到了所有节点的最短距离。

我们的闹钟算法如下:

  • 讲S的闹钟设为0
  • 循环,直到没有任何一个闹钟 假设,下一个闹钟(距离最近的节点)响起响起的时间是T,到达的节点是U,那么
    • 从S到U的距离就是T
    • 对于U的每一个相邻节点V
      • 如果v还没有闹钟,则将它的闹钟设置为 T + l(u, v)
      • 如果v的闹钟,比 T + l(u,v)晚,则更新v的闹钟

Dijkstra实现

我们来看下具体实现,实现算法可以帮助我们进一步理解算法。

class Dijkstra
  INFINITY = 1 << 32
  def initialize(weighted_graph)
    @weighted_graph = weighted_graph
  end

  def shortest_distances
    make_alarms
    decrease_alarm(0, 0)

    while v = alarm!
      @weighted_graph[v].each do |w, weight|
        if alarm(w) > alarm(v) + weight
          decrease_alarm(w, alarm(v) + weight)
        end
      end
    end

    @alarms
  end

  def make_alarms
    @vertexes_alarms = (0...vertexes_count).to_a

    @alarms = Array.new(vertexes_count, INFINITY)
  end

  def alarm(vertex)
    @alarms[vertex]
  end

  def decrease_alarm(vertex, time)
    @alarms[vertex] = time

    @vertexes_alarms.sort_by! do |vertex|
      @alarms[vertex]
    end
  end

  def alarm!
    @vertexes_alarms.delete_at(0)
  end

  def vertexes_count
    @vertexes_count ||= @weighted_graph.length
  end
end


优化

自己观察这个算法,会发现decrease_alarm这个方法,每次都调用了sort!方法。但其实我们每次拿出来的闹铃都是数值最小的那一个,用优先队列(Priority queue)更合适。这样可以降低算法的复杂度,让我们的算法更快。

总结

算法的书有很多,但讲清楚算法是怎么来的,却很少。《Algorithms》这本书采用的方式,很像《怎样解题》所采用方式,很有趣,也很有启发性。

同时算法最有趣的地方在于可以一点一点改进和优化!

原文链接

参考

  1. Algorithms
  2. 算法导论
  3. 怎样解题
  4. 画图网站
共收到 8 条回复
1107 jasl 将本帖设为了精华贴 2月03日 01:40
23956

挺好的,顺便po一个地址算法可视化.

23196

马克学习!好帖!

15940

大一狗看的心花怒放 😉 十分适合初学者理解dijkstra算法工作流程的文章!

还有以下一个小错误?10是不是改成100

假设从S到U的距离是10,那么计算前99个哑节点的距离,都是没有意义的。

7072

#4楼 @somejump 😃 大一就开始学ruby了,👍 👍

多谢多谢,已更正!

7533

补充个实例用法

weighted_graph=[
  [[0,0],[1,100],[2,200]],
  [[0,100],[1,0],[2,50]],
  [[0,200],[1,50],[2,0]]
]

graph = Dijkstra.new(weighted_graph)
graph.shortest_distances
puts graph
8744

这个思路有趣!

4156

priority queue也就是堆。实现一个堆并不难。而且dijkstra中的堆使用并不需要堆排序,只需要维护一个小根堆就可以了。复杂度可以降低到 O((V+E) lg V)。而注意到复杂度中包含了E,说明这个算法对稀松图是非常适合的

需要 登录 后方可回复, 如果你还没有账号请点击这里 注册