[Ruby] ワーシャルフロイド法

名前も実装もかっこいいアルゴリズムのワーシャルフロイド法をrubyで実装する。

重み付きで有向な、しかもコストが正の場合に、全点間の最小コストを非常に簡潔にかくことができるもの。

INF = 9999999.freeze

nodes_size = gets.chomp.to_i.freeze
edges_size = gets.chomp.to_i.freeze
edges = []

# nodes初期化
nodes_size.times do |i|
  nodes_size.times do |j|
    edges[i] ||= []
    edges[i][j] = INF
  end
  edges[i][i] = 0
end

# データ読み込み
edges_size.times do |i|
  edge = gets.split(' ').map(&:to_i)
  edges[edge[0]] ||= []
  edges[edge[0]][edge[1]] = edge[2]
end

# ワーシャルフロイド
nodes_size.times do |i|
  nodes_size.times do |j|
    nodes_size.times do |k|
      edges[i][j] = [edges[i][j], edges[i][k] + edges[k][j]].min
    end
  end
end

標準入力からの入力例を用意した。
こんなグラフになっている。

5
12
0 1 1
1 0 1
0 2 5
2 0 5
1 2 3
2 1 3
1 4 3
4 1 3
2 3 6
3 2 6
3 4 5
4 3 5

実際のアルゴリズムは23行目以降で、ただの３重ループで実装が終わってしまう。
edges[i][j]に格納されるものは、i点からj点への最小コストとなる。
edgesには初期状態では入力として与えられた経路しかないけれども、キモとなっている２７行目を見てみると、iからjへの最小コストとiからkの最小コスト＋kからjへの最小コストを比較して小さい方でedges[i][j]を更新している。

この中間点kを置くという発想がイケメンですね。