プログラミングコンテストチャレンジブック演習「ダイクストラ法」

今回のお題はこちら。

今回も$costが適切に初期化されていませんが、アルゴリズムはあってます。

INF = 2 ** 30
V = 10
$cost = Array.new( V ).map!{ Array.new( V, INF ) }

$d = Array.new(V, INF)
$used = Array.new(V, false)

def dijkstra(s)
  d[s] = 0

  while true
    minV = -1

    for i in 0..(v - 1)
      minV = i if !$used[i] && (minV == -1 || d[minV] > d[i])
    end
    break if minV == -1

    $used[minV] = true
    for i in 0..(V - 1)
      d[i] = [d[i], d[minV] + $cost[minV][u] ].min
    end
  end
end