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

今回のお題はこちら。

$costに各頂点間のコストをいれれば全点対最短路が計算できます。
実装が簡単なのがいいですな。

V = 10 #input
$cost[V][V] #input

def warshall_floyd
  for k in 0..(V - 1)
    for i in 0..(V - 1)
      for j in 0..(V - 1)
        $cost[i][j] = [$cost[i][j], $cost[i][k] + $cost[k][j]].min
      end
    end
  end
end

puts $cost