Dijkstra

Dijkstra算法描述为:假设用带权邻接矩阵来表示带权有向图。首先引进一个辅助向量D,它的每个分量D[i]表示当前所找到的从始点v到每个终点Vi的最短路径。它的初始状态为:若两顶点之间有弧,则D[i]为弧上的权值;否则置D[i]为无穷大。

u 找到与源点v最近的顶点,并将该顶点并入最终集合S

u 根据找到的最近的顶点更新从源点v出发到集合VS上可达顶点的最短路径;

u 重复以上操作。

1 带权有向图

以前总是认为Dijkstra算法可以用来求从源点到指定终点的最短路径,导致总不能抓住算法的中心思想。现在认为把握Dijkstra的算法要点为:

u Dijkstra提出了一个按路径长度递增的次序产生最短路径的算法;

u 每次循环都可以得到一个从源点到某个顶点的最短路径,某个即不是确定的一个;

以带权有向图1为例说明Dijkstra算法的执行过程:假设源点为v0,则初始状态时源点到其它各顶点的距离为:

源点 终点

v1

v2

v3

v4

v5

v0

10

30

100

由上表可知,与源点v0最近的顶点为v2,距离为10

v2加入到最终顶点集合S中。

再根据v2更新从源点到其它顶点的最短距离,即从v0v2v3的距离为60<∽,所以将v0v3的距离更新为60,如下表所示:

源点 终点

v1

v2

v3

v4

v5

v0

10

60

30

100

由上表可知,与源点v0次近的顶点为v4,距离为30

v4加入到最终顶点集合S中;

再根据v4更新从源点到其它顶点的最短距离。即从v0v4v3的距离为50<60,所以将v0v3的距离更新为50;从v0v4v5的距离为90<100,所以将v0v5的距离更新为90

源点 终点

v1

v2

v3

v4

v5

v0

10

50

30

90

重复以上操作……

直到最终集合包含了所有的顶点。

RubyChina 提供的ruby版源码

我们的闹钟算法如下:

  • 讲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

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

优化

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

总结

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

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

原文链接

参考

  1. Algorithms
  2. 算法导论
  3. 怎样解题
  4. 画图网站

发表评论

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