2026-10-28
NegativeCycle.hs
hasNegativeCycle :: Int -> [(Int, Int, Int)] -> Bool
頂点が 0 から n - 1 まで n 個あり、辺 (u, v, w) は頂点 u から頂点 v へ重み w で進めることを表します。辺をたどって出発した頂点に戻る道筋のうち、重みの合計が負になるものが1つでもあれば True を返す hasNegativeCycle n edges を書いてください。w は負でもよく、自分自身に戻る辺もあります。n は1以上で、辺が無ければ False です。
入力例 1
hasNegativeCycle 3 [(0, 1, 2), (1, 2, -3), (2, 0, 0)]
出力例 1
True
入力例 2
hasNegativeCycle 3 [(0, 1, 2), (1, 2, -3), (2, 0, 1)]
出力例 2
False
入力例 3
hasNegativeCycle 1 []
出力例 3
False
Reference
import qualified Data.Map as Map
hasNegativeCycle :: Int -> [(Int, Int, Int)] -> Bool
hasNegativeCycle n edges = relax (rounds !! n) /= rounds !! n
where
start = Map.fromList [(v, 0) | v <- [0 .. n - 1]]
rounds = iterate relax start
relax dist = foldl update dist edges
update dist (u, v, w) = Map.adjust (min (dist Map.! u + w)) v dist
各頂点に距離の値を持たせ、すべての辺 (u, v, w) について「v の値を、u の値に w を足したものより大きくしない」更新を何回も繰り返します。重みの合計が負になる閉路が無ければ、どの値も同じ頂点を2度通らない道筋の長さで決まり、そうした道筋は辺を高々 n - 1 本しか使わないので、n - 1 回の繰り返しで値は変わらなくなります1。負の閉路があれば、その上の頂点の値は回るほど下がるので、何回繰り返しても値が変わり続けます。
どの閉路を探すかは決まっていないので、全頂点の値を0から始めます。これは、全頂点へ重み0の辺を持つ出発点を1つ足したのと同じで、頂点が1つ増えた分、値が決まるまでに最大 n 回かかります。そこで n 回繰り返した rounds !! n に、もう1回 relax をかけて値が変われば、負の閉路があります。入力例1は0→1→2→0の重みの合計が -1 なので True、入力例2は合計が0で負ではないので False です。
掲載したのは参考実装で、唯一の正解ではありません。距離を Data.Map に持ちましたが、リストで持って !! で引いても同じ結果になります。
- この繰り返しはベルマン・フォード法(Bellman-Ford algorithm)と呼ばれる最短経路の求め方で、ふつうは出発点を1つ決め、その値だけを0、ほかを無限大として始めます。