日々精進

新しく学んだことを書き留めていきます

プログラミングコンテストチャレンジブック演習「ベルマンフォード法」

今回のお題はこちら。

横着して$edgeに入力値を代入してないですが、アルゴリズムはあってます。

V = 7 #input
E = 10 #input
$edges = Array.new #input
INF = 2 ** 30

$d = Array.new(V, INF) #各頂点への最短距離
while true
  update = false
  for i in 0..(E - 1)
    edge = $edges[i]
    if d[edge.to] > d[edge.from] + edge.cost
      d[edge.to] = d[edge.from] + edge.cost
      update = true
    end
  end

    break unless update
end