読者です 読者をやめる 読者になる 読者になる

閉路の検出に負辺が入るとつらい

アルゴリズム

今回つまづいた問題はAOJでライブラリのverify向けの問題として公開されているAll Pairs Shortest Pathです。負の辺があり得る有向グラフ(|E| <= 9900, |V| <= 100, 多重辺や自己ループは無し)が与えられるので、負閉路が存在するなら"NEGATIVE CYCLE"を出力、そうでなければ各頂点間の最短経路の長さを隣接行列みたいに出力せよ、ただし頂点間に経路が無ければ最短経路の長さの代わりに"INF"と出力せよ、という問題です。

問題を読んですぐに

  • 「All Pairs Shortest Pathで…」(ワーシャル―フロイド法かな…)
  • 「|V| <= 100で…」(ワーシャル―フロイド法かな…)
  • 「負閉路が存在するなら"NEGATIVE CYCLE"を出力」(ワーシャル―フロイド法だ!)

ということまでは思いつきましたが、3つ目の「負閉路が存在するなら〜」ということに関しては「ワーシャル―フロイド法でも検出できるらしい」ということを知識として知っているだけで、実際に負の辺をもつグラフに対してワーシャル―フロイド法を適用したことはありませんでした。

そういうわけで負の閉路の検出方法についてはググりながら、辺のコストが非負のグラフと同じ要領でワーシャル―フロイド法を書いて提出すると、見事にWA。ここでちゃんと考察していればよかったのですが、「ワーシャル―フロイド法なんて今までに何十回と書いてきたんだからワーシャルフロイド法のところ以外でバグっているに違いない」と思い込んでしまい、修正になっていない修正を送りつけてWAを連発させ、事あるごとに書き直しをしていると数週間が経ってしまいました。

いつまでたってもACする気配が無いので他に人の解法を参考にしていると、ワーシャル―フロイド法の3重ループの中で見慣れないif文が入っていることに気づきました。まさかと思って自分のコードに同じものを入れてみるとそれだけでAC。問題のコードはこれこれです。26行目のif文を書いていると通り、コメントアウトすると落ちます。

どういうことか全く分からなかったのでTwitterで助けを求めてみました。

一度教えてもらうとすぐに分かる類のバグなのですが、WAになるコードの撃墜ケースは以下の様なものです。

f:id:kujira16:20140514172313j:plain

頂点間の最短経路の長さをd[i][j]みたいに格納しているとすると、

d[A][C] = min(d[A][C], d[A][B]+d[B][C]);

みたいに普段なら書くと思いますが、負の辺が存在するときにはこれはバグります。そのため、負の辺を持つグラフにおいてはこれの前に

if(d[A][B] != INF && d[B][C] != INF)

が必要です。