2026-10-28
Walks.hs
edges :: [(Int, Int, Int)]
edges = [(0, 1, 1), (1, 2, -2), (2, 1, 1)]
step :: [Int] -> [Int]
step ds = [minimum (ds !! v : [ds !! u + w | (u, t, w) <- edges, t == v]) | v <- [0 .. 2]]
main :: IO ()
main = print (iterate step [0, 1000000, 1000000] !! 1000)
これは何を出力するでしょうか?
Answer
[0,-498,-500] です。
edges の (u, t, w) は、頂点 u から頂点 t へ重み w で進める辺です。step は各頂点 v について、いまの値 ds !! v と、v に入る辺ごとの ds !! u + w のうち最小のものを新しい値にします。新しい値はどれも前の回のリスト ds だけから計算するので、1回の step で辺を1本ずつ伸ばす形になります。
1000回を順に追う代わりに、k 回目のあとの値が何を表しているかを考えます。辺を順にたどる道筋(同じ頂点を何度通ってもよい)の重みの合計を道筋の長さと呼ぶと、k 回目のあとの ds !! v は、頂点0から v へ辺を k 本以下使って行く道筋の長さの最小値です。0回目は頂点0が辺0本の0で、ほかは道筋がまだ無い印の1000000です。k + 1 本以下の道筋は、k 本以下で済んでいるか、k 本以下で u まで来て最後に辺 (u, v, w) を足したものなので、step の最小値がちょうどその最小値になります。1000000から作った値は、本物の道筋が見つかるとすぐに負けるので、答えには残りません。
頂点0に入る辺は無いので、頂点0は0のままです。頂点1へは、辺 (0, 1, 1) の1本で長さ1、そこから1→2→1と回るたびに辺が2本増えて長さが -2 + 1 で1ずつ減ります。辺を1000本まで使えるので、1 + 2 * 499 の999本で回れるのは499周で、最小値は 1 - 499 の -498 です。頂点2へは0→1→2の2本で長さ -1、同じく 2 + 2 * 499 の1000本で499周できるので -500 になります。
頂点の数より1回少ない2回で値が決まると考えると、2回目の [0,1,-1] と答えてしまいます1。1→2→1の閉路は長さが -1 なので、回るほど値は下がり続け、決まった値に落ち着くことはありません。それでも1000回で止めれば、使える辺の本数で周回の数が決まり、値は1つに決まります。
- 辺を1本ずつ伸ばしながら最小値を更新するこの手順は、ベルマン・フォード法(Bellman-Ford algorithm)です。頂点が n 個で長さが負になる閉路が無ければ、同じ頂点を2度通らない道筋で足りるので、n - 1 回で値が決まります。