練習のための問題は 競技プログラミングの履歴
重み付き有向グラフの全ペアの最短経路問題を多項式時間で解くアルゴリズムである。
- ダイクストラ法 は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