フロイド−ワーシャル・アルゴリズム(Ruby)


フロイド−ワーシャル・アルゴリズムは、グラフの全点から全点へのすべての最短経路を求めます。重みは負値を許しますが、負閉路は許しません。

上のようなグラフは次のようなハッシュで表現されます。頂点を表わすオブジェクトは何でもかまいません。

g = {a: {b: 3, c: 8}, b: {d: 1}, c: {b: 4}, d: {a: 2, c: -5}}

これは Hash#to_graph によって次のような配列に変換されます。

[[0, 3, 8, Infinity],
 [Infinity, 0, Infinity, 1],
 [Infinity, 4, 0, Infinity],
 [2, Infinity, -5, 0]]

メソッドの内部では @tr = {0=>:a, 1=>:b, 2=>:c, 3=>:d} というハッシュによって、頂点と頂点をあらわす番号(頂点番号)との間が関係づけられています。配列[from][to] は、from, to の頂点番号により、経路の重みを表現しています。Infinity は経路が存在しません。

メソッド Array#floyd_warshall は、その配列から全点最短経路を求めます。返り値は [shortest, pred] で、shortest も pred も(頂点数を n とすると) (n + 1) × n × n の大きさの配列です。具体的には

shortest =
[[[0, 3, 8, Infinity],
  [Infinity, 0, Infinity, 1],
  [Infinity, 4, 0, Infinity],
  [2, Infinity, -5, 0]],
 [[0, 3, 8, Infinity],
  [Infinity, 0, Infinity, 1],
  [Infinity, 4, 0, Infinity],
  [2, 5, -5, 0]],
 [[0, 3, 8, 4],
  [Infinity, 0, Infinity, 1],
  [Infinity, 4, 0, 5],
  [2, 5, -5, 0]],
 [[0, 3, 8, 4],
  [Infinity, 0, Infinity, 1],
  [Infinity, 4, 0, 5],
  [2, -1, -5, 0]],
 [[0, 3, -1, 4], [3, 0, -4, 1], [7, 4, 0, 5], [2, -1, -5, 0]]]
pred =
[[[nil, 0, 0, nil], [nil, nil, nil, 1], [nil, 2, nil, nil], [3, nil, 3, nil]],
 [[nil, 0, 0, nil], [nil, nil, nil, 1], [nil, 2, nil, nil], [3, 0, 3, nil]],
 [[nil, 0, 0, 1], [nil, nil, nil, 1], [nil, 2, nil, 1], [3, 0, 3, nil]],
 [[nil, 0, 0, 1], [nil, nil, nil, 1], [nil, 2, nil, 1], [3, 2, 3, nil]],
 [[nil, 0, 3, 1], [3, nil, 3, 1], [3, 2, nil, 1], [3, 2, 3, nil]]]

となります。いずれも最後の 2次元行列が求めるべき回答です。shortest の最後は重みの最小値を、pred の最後はたどるべき経路を表します。例えば頂点 0 から頂点 2 の重みの最小値は shortest[4][0][2] = -1 となり、最短経路は 0→1→3→2 となります。最短経路は後ろから pred[4][0][2] = 3 で頂点 3、pred[4][0][3] = 2 で頂点 2、pred[4][0][2] = 0 で頂点 0 という具合です。

この結果、この場合での最短経路中の最大値は shortest[4][2][0] = 7 であり、つまりは頂点 2 から 0 の経路ということがわかります。

メソッド Hash#order(from, to) は Array#floyd_warshall を呼び出したあと、頂点 from から to までの最短経路(経路番号ではありません)を順に配列に入れて返します。

floyd_warshall.rb

class Array
  def floyd_warshall
    #Float or Integer or Rational{ar[][], shortest[][][], a}, Integer{pred[][][]}, size
    ar = self
    size = ar.size
    class << ar
      def include?(u, v)
        self[u][v] != Float::INFINITY and !self[u][v].zero?
      end
    end
    
    shortest = Array.new(size + 1) {Array.new(size) {Array.new(size)}}
    pred     = Array.new(size + 1) {Array.new(size) {Array.new(size)}}
    size.times do |u|
      size.times do |v|
        shortest[0][u][v] = ar[u][v]
        pred[0][u][v] = ar.include?(u, v) ? u : nil
      end
    end
    
    size.times do |x|
      size.times do |u|
        size.times do |v|
          if shortest[x][u][v] > (a = shortest[x][u][x] + shortest[x][x][v]) 
            shortest[x + 1][u][v] = a
            pred[x + 1][u][v] = pred[x][x][v]
          else
            shortest[x + 1][u][v] = shortest[x][u][v]
            pred[x + 1][u][v] = pred[x][u][v]
          end
        end
      end
    end
    
    [shortest, pred]
  end
end

class Hash
  def to_graph
    #Object{node[]}, Float or Integer or Rational{ar[][]}
    #Hash{@tr[Integer]: Object}
    
    node = keys
    @tr = node.map.with_index {|key, i| [i, key]}.to_h
    ar = Array.new(size) {Array.new(size, Float::INFINITY)}
    
    size.times do |x|
      self[@tr[x]].each do |g|
        ar[x][node.index(g[0])] = g[1] 
      end
      ar[x][x] = 0
    end
    ar
  end
  
  def order(from, to)
    #Object{from, to} ->
    #Object{ans[]}, Hash{tr[Object]: Integer}
    #Integer{pred[][][], ar[][], from1, nxt}, shortest
    
    shortest, pred = to_graph.floyd_warshall
    ar = pred[-1]
    tr = @tr.invert
    from1 = tr[from]
    ans = [to]
    nxt = ar[from1][tr[to]]
    
    while nxt != from1
      ans.unshift(@tr[nxt])
      nxt = ar[from1][nxt]
    end
    [@tr[nxt]] + ans
  end
end

if __FILE__ == $0
  g = {a: {b: 3, c: 8}, b: {d: 1}, c: {b: 4}, d: {a: 2, c: -5}}
  p g.order(:a, :c)    #=>[:a, :b, :d, :c]
end

 

アルゴリズムの基本

アルゴリズムの基本