フロイド−ワーシャル・アルゴリズムは、グラフの全点から全点へのすべての最短経路を求めます。重みは負値を許しますが、負閉路は許しません。
上のようなグラフは次のようなハッシュで表現されます。頂点を表わすオブジェクトは何でもかまいません。
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
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
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)
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)
end
