ダイクストラ法

ダイクストラ法を作ってみました。
グラフは、ラベルつき隣接行列にしたのですが、辺が存在しないところを、nilで表現したのがまずかったです。条件判断などが繁雑になってしまいました。

threadの学習を兼ねて使ってみました。
dijkstra.rb

class Dijkstra
  attr_reader :result
  def initialize(g)
    @graph = g
  end

  def dijkstra(start)
    vertex = Array.new          # 頂点の集合
    @graph.size.times{|i| vertex << i}
    visited = Array.new         # 訪問済みの集合
    visited << start
    dist = @graph[start].dup    # dist[index]までの最短距離
    (@graph.size - 1).times do 
      # 未訪問の頂点からdist[w]が最小な頂点を選択
      w = search_vertex(vertex - visited, dist)
      if w != nil
        visited << w 
        (vertex - visited).each do |val|
          if @graph[w][val] && dist[val]
            dist[val] = if dist[val] < dist[w] + @graph[w][val]
                          dist[val]
                        else
                          dist[w] + @graph[w][val]
                        end
          elsif @graph[w][val]
            dist[val] = dist[w] + @graph[w][val]
          end
        end
      end
    end
    @result = dist
  end

  def search_vertex(v_s, d)
    min = nil
    v_s.each do |v|
      next if d[v] == nil
      min = d[v] if min == nil || min > d[v]
    end
    return nil if min == nil
    d.each_with_index do |val, idx|
      return idx if d[idx] == min
    end
  end
end

if __FILE__ == $0
  Graph = [[nil,  10, nil,  30, 100],
           [nil, nil,  50, nil, nil],
           [nil, nil, nil, nil,  10],
           [nil, nil,  20, nil,  60],
           [nil, nil, nil, nil, nil]]
  threads = []
  Graph.size.times do |i|
    threads << Thread.new(i) do |i|
      sleep(rand * 10)
      dijk = Dijkstra.new(Graph)
      dijk.dijkstra(i)
      print "#{i}: ", dijk.result.join(', '), "\n"
    end
  end
  threads.each{|t| t.join}
end

実行結果

mmasa@debian:~/work/ruby$ ruby dijkstra.rb
0: , 10, 50, 30, 60
4: , , , ,
3: , , 20, , 30
1: , , 50, , 60
2: , , , , 10

sleep(rand * 10)が効いているので、出力順がランダムになっています。出力が見にくいですが、例えば、頂点0からは、頂点1へ最短距離が10、頂点2へ最短距離が50…となっています。数字が表示されていないところへは、たどり着くことができません。頂点4からは、どこへも行けません。