Bellman-Ford의 n번째 라운드에서 갱신되는 정점이 있으면 왜 source-reachable negative cycle을 의미하나요?

n-1회 동안 모든 간선을 완화한 뒤에도 dist[v]를 낮출 수 있다는 것은 source에서 v까지 더 긴 walk가 기존의 모든 단순 경로보다 싸다는 뜻입니다. source-reachable negative cycle이 없다면 cycle을 제거해도 더 나빠지지 않는 단순 최단 경로가 존재하고, 그 경로는 최대 n-1개 간선으로 표현됩니다. 따라서 n번째 라운드의 갱신은 cycle을 포함한 경로가 계속 비용을 낮추고 있다는 신호입니다.

단, 갱신 조건에 dist[u] != INF를 넣어야 합니다. source에서 닿지 않는 음수 cycle은 그 영역의 거리를 낮추지만 single-source 결과에는 영향을 주지 않습니다. 예를 들어 S가 A에만 닿고 X↔Y가 별도 요소라면 X,Y는 계속 미도달 상태입니다.

갱신되는 정점 하나를 기록했다고 모든 정점이 -INF라는 뜻은 아닙니다. cycle에 도달할 수 있고 cycle에서 target으로 나갈 수 있는 쌍만 유한 최단값이 없습니다. 그래서 cycle 영향까지 표현하려면 갱신 후보를 seed로 다시 도달성 탐색하거나, cycle 정점을 복원한 뒤 source-to-cycle 및 cycle-to-target 조건을 검사합니다. 출력은 finite, unreachable, negative-cycle-affected를 구별해야 합니다.

실제 trace에서 간선 순서를 S-A, A-B, B-A로 두면 시작 [0,INF,INF], 첫 pass 뒤 [0,-2,2], 다음 pass에서 B-A가 다시 내려가며 갱신이 계속됩니다. n-1=2회 뒤에도 갱신이 남는다는 사실이 단순 경로 상한과 모순되므로 cycle을 포함한 walk가 원인입니다. 갱신된 v 하나가 cycle의 모든 정점이라는 뜻은 아니어서 parent를 n번 따라가 cycle 내부로 들어가는 복원 단계와, cycle에서 각 target으로 나가는 탐색을 분리합니다. cycle에 닿지 않는 X-Y의 dist는 INF로 남고, cycle에 도달하지만 출구가 없는 target은 affected가 아닙니다. 따라서 boolean 하나가 아니라 target별 상태가 필요합니다.