Dijkstra

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

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

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

u 重复以上操作。

图1 带权有向图

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

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

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

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

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

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

再根据v2更新从源点到其它顶点的最短距离，即从v0–v2–v3的距离为60<∽，所以将v0到v3的距离更新为60，如下表所示：

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

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

再根据v4更新从源点到其它顶点的最短距离。即从v0–v4–v3的距离为50<60，所以将v0到v3的距离更新为50；从v0–v4–v5的距离为90<100，所以将v0到v5的距离更新为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. 画图网站