Rubyで行列掛け算法による最短距離計算

行列掛け算法による最短距離の計算をするプログラム。

#一行に"元のnode 行き先のnode length"としているファイルを読み込み
#そこから行列掛け算法を用いてノード間最短距離を求める
 
class Times_matrix
  def initialize
    # nodeに番号をふるhash
    @node = Hash.new
    # ノード間の距離行列
    @matrix = Array.new
    File.open(ARGV[0]) do |file|
      i = 0
      # ファイルからのノード間距離の読み込み
      while text = file.gets do
        graph = text.split(" ")
        if @node[graph[0]] == nil then
          @node[graph[0]] = i
          i += 1
        end
        if @node[graph[1]] == nil then
          @node[graph[1]] = i
          i += 1
        end
        from = @node[graph[0]]
        to = @node[graph[1]]
        @matrix[from] = Array.new if @matrix[from] == nil
        @matrix[from][to] = graph[2].to_i
      end
      #繋がっていないノード間をinfinityにする
      @node.length.times do |i|
        @matrix[i][i] = 0
        @node.length.times do |j|
          @matrix[i][j] = 1/0.0 if @matrix[i][j] == nil
        end
      end
    end
  end
  def calculate
    # 掛け算の反復回数
    n = @node.length - 1
    n.times{one_step}
  end
  # 行列掛け算法
  def one_step
    new_matrix = Array.new
    n = @node.length
    n.times do |i|
      new_matrix[i] = Array.new
      n.times do |j|
        path = Array.new
        n.times do |k|
          l = @matrix[i][k] + @matrix[k][j]
          path.push l
        end
        min_l = 1/0.0
        # 最小のpathを選ぶ
        path.each{|l| min_l = l if min_l >= l}
        new_matrix[i][j] = min_l
      end
    end
    @matrix = new_matrix
  end
  # ノード間の最短距離を表示
  def print_min
    n = @node.length
    n.times do |i|
      from = @node.index(i)
      n.times do |j|
        to = @node.index(j)
        next if i == j
        print "#{from}から#{to}への最短距離は#{@matrix[i][j]}\n"
      end
    end
  end
end
 
a = Times_matrix.new
a.calculate
a.print_min
 

因数で与えるファイルは
元のノード 行き先のノード エッジの長さ
をスペース区切りで一行ずつ描いておく。
例えばこんな感じ

a b 1
a c 3
a d 6
b c 1
c b 5
c d 1
d a 1
d c 5

実行すると次のようになる

aからbへの最短距離は1
aからcへの最短距離は2
aからdへの最短距離は3
bからaへの最短距離は3
bからcへの最短距離は1
bからdへの最短距離は2
cからaへの最短距離は2
cからbへの最短距離は3
cからdへの最短距離は1
dからaへの最短距離は1
dからbへの最短距離は2
dからcへの最短距離は3