トップ 差分 一覧 ソース 検索 ヘルプ RSS ログイン

ワーシャルフロイド法

[アルゴリズム,グラフアルゴリズム]

練習のための問題は 競技プログラミングの履歴

重み付き有向グラフの全ペアの最短経路問題を多項式時間で解くアルゴリズムである。

  • ダイクストラ法 は1つペアの最短経路を求めるアルゴリズムだったが、ワーシャルフロイド法はその複数バージョンと考えることもできる
  • 計算量は O(|V^3|) になるのですが、LL言語だとプロコンでTLEになる可能性がわりかしある
    • コンパイル言語で実装を作っておこう

ワーシャルフロイド法

  詳しい解説

疑似コード

  • 以下で、経路の長さが無限大は経路がないことを意味している。di,j は pi,j の長さ。di,j を更新する際、経路も記録すると、pi,j も求めることができる。
グラフ G = (V, E) および各辺 e ∈ E の長さ length(e) を入力として受け取る。

// 初期化
for each i ∈ {1,...,n}
    for each j ∈ {1,...,n}
        di,j ← i と j を結ぶ辺 e があれば length(e) なければ 無限大

// 本計算
for each k ∈ {1,...,n}
    for each i ∈ {1,...,n}
        for each j ∈ {1,...,n}
            if (di,j > di,k + dk,j)
                di,j ← di,k + dk,j
  • Rubyコードに落とし込む
#
# :u ノードのインデックス
# :k u の出次数
# :v u に隣接する頂点の番号
# :w 隣接する頂点への重み
#
INF  = Float::INFINITY
Node = Struct.new(:u, :k, :v, :w)
 
class Graph
  attr :nodes, :dist
  def initialize(n)
    @nodes = Array.new(n){ Node.new }
    @nodes = @nodes.map.with_index do |node,idx|
      node.u = idx
      node
    end
    @dist = Array.new(n).map{Array.new(n, 0)}
  end
 
  def add_graph_edge(u, v, w)
    #puts "#{u} -> #{v} (#{w})"
    if @nodes[u].v.nil?
      @nodes[u].v = [v]
      @nodes[u].w = {v=>w}
    elsif @nodes[u].v.is_a?(Array)
      @nodes[u].v << v
      @nodes[u].w = {v=>w}.merge(@nodes[u].w)
    else
      @nodes[u].v = [@nodes[u].v, v]
      @nodes[u].w = {v=>w}.merge(@nodes[u].w)
    end
    @nodes[u].k = if @nodes[u].v.is_a?(Array)
                    @nodes[u].v.length
                  else
                    1
                  end
  end
 
  def warshall_floyd()
    # initialize
    for i in [email protected]
      for j in [email protected]
        @dist[i][j] = if not @nodes[i].w.nil? and @nodes[i].w.has_key?(j)
                        @nodes[i].w[j]
                      else
                        INF
                      end
      end
      @dist[i][i] = 0
    end
 
    # calc
    for k in [email protected]
      for i in [email protected]
        for j in [email protected]
          if @dist[i][k] != INF and @dist[k][j] != INF
            @dist[i][j] = [@dist[i][j], @dist[i][k] + @dist[k][j]].min
          end
        end
      end
    end
  end
 
  def has_negative_cycle?()
    ans = false
    for v in 0...V
      ans = true if @dist[v][v] < 0
    end
    ans
  end
end

  AOJの関連する問題

  計算量 O(|V^3|)

  • 結構重そうな処理ですねえ

GRL_1_C

解答

  • ポイント
閉路の判定
隣接する頂点への重みを格納している二次元配列(@dist)のうち、@dist[x][x]が埋まっていればそれは閉路の重みの合計になる
無限値の処理
閉路の検出に負辺が入るとつらい 閉路の処理を適切に行わないとバグる
lines = $stdin.read
array = lines.split("\n")
 
#
# :u ノードのインデックス
# :k u の出次数
# :v u に隣接する頂点の番号
# :w 隣接する頂点への重み
#
INF  = Float::INFINITY
Node = Struct.new(:u, :k, :v, :w)
 
class Graph
  attr :nodes, :dist
  def initialize(n)
    @nodes = Array.new(n){ Node.new }
    @nodes = @nodes.map.with_index do |node,idx|
      node.u = idx
      node
    end
    @dist = Array.new(n).map{Array.new(n, 0)}
  end
 
  def add_graph_edge(u, v, w)
    #puts "#{u} -> #{v} (#{w})"
    if @nodes[u].v.nil?
      @nodes[u].v = [v]
      @nodes[u].w = {v=>w}
    elsif @nodes[u].v.is_a?(Array)
      @nodes[u].v << v
      @nodes[u].w = {v=>w}.merge(@nodes[u].w)
    else
      @nodes[u].v = [@nodes[u].v, v]
      @nodes[u].w = {v=>w}.merge(@nodes[u].w)
    end
    @nodes[u].k = if @nodes[u].v.is_a?(Array)
                    @nodes[u].v.length
                  else
                    1
                  end
  end
 
  def warshall_floyd()
    # initialize
    for i in [email protected]
      for j in [email protected]
        @dist[i][j] = if not @nodes[i].w.nil? and @nodes[i].w.has_key?(j)
                        @nodes[i].w[j]
                      else
                        INF
                      end
      end
      @dist[i][i] = 0
    end
 
    # calc
    for k in [email protected]
      for i in [email protected]
        for j in [email protected]
          if @dist[i][k] != INF and @dist[k][j] != INF
            @dist[i][j] = [@dist[i][j], @dist[i][k] + @dist[k][j]].min
          end
        end
      end
    end
  end
 
  def has_negative_cycle?()
    ans = false
    for v in 0...V
      ans = true if @dist[v][v] < 0
    end
    ans
  end
end
 
V,E = array[0].split(" ").map(&:to_i)
graph = Graph.new(V)
 
array[1..E].each do |s|
  s,t,d = s.split(" ").map(&:to_i)
  graph.add_graph_edge(s,t,d)
end
 
# execute WarshallFloyd !
graph.warshall_floyd()
 
if graph.has_negative_cycle?
  puts "NEGATIVE CYCLE"
else
  graph.dist.each do |d|
    puts d.map{|d| if d == INF; "INF" else d end}.join(" ")
  end
end
お名前: コメント: