フロイド−ワーシャル・アルゴリズム(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
- 作者: トーマス・H・コルメン,長尾高弘
- 出版社/メーカー: 日経BP社
- 発売日: 2016/03/11
- メディア: 単行本
- この商品を含むブログ (5件) を見る