確定できないなら、全部の辺を回数分ゆるめる — Bellman-Ford 法

Bellman 1958 "On a Routing Problem" の Summary(AMS の PDF、2026-10-07 取得)はこう書いています。

The functional equation technique of dynamic programming, combined with approximation in policy space, yields an iterative algorithm which converges after at most (N − 1) iterations.

N は都市の数、つまり頂点の数です。これを実測します。頂点5・有向辺7で、負の辺を含み負の閉路の無いグラフです(Python 3.14.6 / macOS arm64、2026-10-07)。

S→A 4, S→B 2, B→A −3, A→C 3, B→C 6, C→D −1, B→D 8

正解は S=0, A=−1, B=2, C=2, D=1 です。最短路 S→B→A→C→D は辺4本で、ちょうど V−1 本です。

辺を逆順(C→D, A→C, B→A, S→B, S→A, B→C, B→D)に並べて周回すると、こうなります。

round 1: {'S': 0, 'A': 4, 'B': 2, 'C': 8, 'D': 10}
round 2: {'S': 0, 'A': -1, 'B': 2, 'C': 7, 'D': 7}
round 3: {'S': 0, 'A': -1, 'B': 2, 'C': 2, 'D': 6}
round 4: {'S': 0, 'A': -1, 'B': 2, 'C': 2, 'D': 1}
round 5: (no change)

A が2周目、C が3周目、D が4周目に正解へ届きます。1周に1本ずつ伝わっています。与えられた順のまま並べると、1周目で全部が正解になりました。

全 7! = 5,040 通りの並び順で、更新があった周回数を数えた分布です。

最大は 4 = V−1 で、最終の距離表はすべて一致しました。

① RIP。 RFC 1058 §1(2026-10-07 取得)はこう書きます。

This memo describes one protocol in a series of routing protocols based on the Bellman-Ford (or distance vector) algorithm.

続く段落は、名前の由来そのものが1つでないことを書いています。

The earliest description of this class of algorithms known to the author is in Ford and Fulkerson [6]. Because of this, they are sometimes known as Ford-Fulkerson algorithms. The term Bellman-Ford is also used. It comes from the fact that the formulation is based on Bellman's equation, the basis of "dynamic programming".

[6] は Ford and Fulkerson "Flows in Networks"(1962)です。「動的計画法」は第6回の主題です。この句は RFC 1058 にだけあり、RIP Version 2 の RFC 2453 §3.1 は based on Bellman's equation [4] で止まります。

RIP にも止まらない更新があります。向きは逆で、値が上がり続けます。§2.1 は到達不能を表す値を決めています。

In the existing implementation of RIP, 16 is used. This value is normally referred to as "infinity", since it is larger than the largest valid metric.

§2.2 はその理由です。

In that case, the metrics may increase slowly in a pattern like the one above until they finally reach infinity. For this reason, the problem is called "counting to infinity".

RIP は値の上限 16 で打ち切ります。引き換えに、RFC 1058 は the protocol was unlikely to be practical for networks with a diameter larger than 15 と書いています。

② 差分制約。 「B は A の3分後以降に始める」は x_A − x_B ≤ −3 と書け、辺 B→A(重み −3)になります。仮の始点から全変数へ重み0の辺を張って最短路を求めると、距離がそのまま開始時刻の候補になります。

3つの作業で「B は A の3分以上後」「C は B の2分以上後」「C は A から L 分以内」とした実測です(Python 3.14.6 / macOS arm64、2026-10-07、頂点4)。

 limit=6 round 1: {'A': -3, 'B': -2, 'C': 0}
limit=6 round 2: {'A': -5, 'B': -2, 'C': 0}
limit=6 round 3: {'A': -5, 'B': -2, 'C': 0} (no change)
limit=4 round 1: {'A': -3, 'B': -2, 'C': 0}
limit=4 round 2: {'A': -5, 'B': -2, 'C': -1}
limit=4 round 3: {'A': -5, 'B': -3, 'C': -1}
limit=4 round 4: {'A': -6, 'B': -3, 'C': -2}

L=6 では3周目で止まります。差だけの制約なので全部に5を足してよく、A=0, B=3, C=5 で全制約を満たします。L=4 では閉路 A→C→B→A が 4 − 2 − 3 = −1 になり、4周目(V 周目)にも下がりました。3分+2分=5分かかるのに4分以内と求めている、矛盾した制約です。