dijkstra.rb

# -*- coding: utf-8 -*-

# 辺
$edge = [[0,1,2],  [0,2,5], [1,2,4],  [1,3,6], 
         [1,4,10], [2,3,2], [3,5,1],  [4,5,3],
         [4,6,5],  [5,6,9], [1,0,2],  [2,0,5],
         [2,1,4],  [3,1,6], [4,1,10], [3,2,2],
         [5,3,1],  [5,4,3], [6,4,5],  [6,5,9]]

# ダイクストラ法
def dijkstra(edge, num_v, start=0)
  # 無限大を定義
  inf = Float::INFINITY

  # 重みを与える
  cost = [*0..num_v].map { [*0..num_v].map { inf }}
  # 各辺と重みに関連付け
  edge.each {|e| cost[e[0]][e[1]] = e[2] }
  # 通過判定
  used = [*0..num_v].map { false }
  # 通過経路
  d = [*0..num_v].map { inf }
  # 開始地点
  d[start] = 0
  
  loop do
    v = -1
    (0..num_v).each do |u|
      # 最もコストの低い移動先を探索
      if !used[u] && (v == -1 || d[u] < d[v])
        v = u
      end
    end

    # 移動先なければ終了
    break if v == -1

    # 通った道を記録
    used[v] = true
    
    # 接続先ノードの情報を更新
    (0..num_v).each do |x|
      d[x] = d[x] < d[v]+cost[v][x] ? d[x] : d[v]+cost[v][x]
    end
    
    # 通過ルートを出力
    p d
  end
  # 最終的なスコア(通過ルートのコストの総和)
  d[num_v]
end

# 実行例
if __FILE__ == $0
  p dijkstra $edge, 6
end