Namaran

Code daily. Without assist.

2026-10-23

relax_rounds.cpp

#include <array>
#include <print>
#include <vector>

int main() {
    const std::vector<std::array<int, 3>> edges{{0, 1, 2}, {2, 3, 1}, {1, 2, -3}, {0, 2, 5}};
    const int inf = 1'000'000;
    std::vector<int> dist{0, inf, inf, inf};
    for (int round = 0; round < 3; ++round) {
        for (const auto& [from, to, w] : edges) {
            if (dist[from] != inf && dist[from] + w < dist[to]) {
                dist[to] = dist[from] + w;
            }
        }
        std::println("{} {}", dist[2], dist[3]);
    }
}

これは何を出力するでしょうか?

Answer

-1 1000000、-1 0、-1 0 の3行です。

edges の各要素は「始点、終点、重み」の辺で、dist は頂点0からの距離の見積もりです。内側のループは辺を書いた順に1本ずつ見て、始点まで来てその辺を通るほうが短ければ、終点の見積もりをその場で書き換えます。この操作を辺の緩和(relaxation)といい、すべての辺を緩和する周回を頂点の数より1少ない回数だけ繰り返す方法を Bellman-Ford 法といいます。負の重みの辺があっても、負の閉路(一周して元の頂点に戻る経路のうち、重みの合計が負のもの)がなければ最短距離が求まります。

1周目は、まず辺 0→1 で dist[1] が2になります。次の辺 2→3 は、この時点で dist[2] がまだ inf なので飛ばされます。3本目の辺 1→2 は、直前に書き換わったばかりの dist[1] を同じ周のうちに使い、dist[2] を 2 + (-3) = -1 にします。最後の辺 0→2 の5は -1 より大きいので、dist[2] は一度も5になりません。周の終わりに dist[3] は inf のままで、1行目は -1 1000000 です。

頂点3の見積もりが入るのは2周目で、辺 2→3 が -1 + 1 = 0 にします。3周目に書き換わる見積もりはありません。周の前の値だけを使って周ごとに一斉に更新すると考えると、1周目は 5 1000000、2周目は -1 6 になり、3周目でようやく -1 0 に追いつきます。このコードは書き換えた値をその周の残りの辺がすぐ使うので、辺の並びが経路の順に合っている部分は1周で何段も先へ進み、合っていない 2→3 のところで1周待たされます。