Bellman-Ford에서 INF에 음수 가중치를 더하면 어떤 오류가 생기며 어떻게 막나요?

INF는 실제 거리 값이 아니라 도달하지 않았다는 표식이므로, dist[u] == INF인 상태에서 가중치를 더하면 안 됩니다. INF=MAX_INT64에서 INF+(-5)는 범위 안의 MAX_INT64-5이지만 sentinel 오염으로 거짓 경로를 만듭니다. 실제 overflow는 MAX_INT64+5 또는 MIN_INT64-5 같은 유한 덧셈입니다.

완화 순서는 먼저 도달성 검사, 다음 유한 값의 checked addition, 마지막으로 비교·대입이어야 합니다. dist[u] != INF인지 확인하고 checked_add(dist[u], w)가 성공할 때만 후보를 만듭니다. 유한 거리끼리 더하는 경우에도 양의 overflow나 음의 underflow가 가능하므로 넓은 타입이나 checked 연산을 사용합니다.

음수 cycle로 값이 계속 내려가는 상태도 실제 최소 정수값으로 저장하지 않는 편이 좋습니다. n번째 라운드 갱신을 별도 seed로 기록해 NEGATIVE_CYCLE_REACHABLE 같은 상태로 표현하면 유한한 큰 음수와 무한 하강을 구분할 수 있습니다. overflow는 입력 범위 오류이고 negative cycle은 그래프 의미의 결과이므로 같은 실패 코드로 섞지 않겠습니다.

수치를 분리해 테스트해야 합니다. INF=MAX_INT64에서 -5를 더한 MAX_INT64-5는 표현 범위 안이지만 sentinel 오염이며, MAX_INT64+5는 양의 overflow입니다. 반대로 MIN_INT64-5는 음의 underflow입니다. 구현 순서는 dist[u] != INF 확인, checked_add, 후보 비교의 세 단계여야 하며, overflow 반환을 wraparound 숫자로 바꾸면 안 됩니다. n번째 pass에서 계속 내려가는 negative cycle은 수치 overflow가 아니라 그래프 의미상 유한 최단값이 없는 상태이므로 별도 seed와 도달성 탐색으로 표현합니다. 작은 테스트에서 세 상태를 각각 확인하면 두 오류를 섞지 않았음을 검증할 수 있습니다.