Namaran

Code daily. Without assist.

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 に持ちましたが、リストで持って !! で引いても同じ結果になります。

  1. この繰り返しはベルマン・フォード法(Bellman-Ford algorithm)と呼ばれる最短経路の求め方で、ふつうは出発点を1つ決め、その値だけを0、ほかを無限大として始めます。