Bellman-Ford에서 n-1회 모든 간선을 완화하면 충분한 이유와 조기 종료 조건은 무엇인가요?

source에서 도달 가능한 음수 cycle이 없다면 최단 경로를 cycle 없는 단순 경로로 만들 수 있고, 정점이 n개일 때 단순 경로의 간선 수는 최대 n-1개입니다. Bellman-Ford의 각 라운드는 모든 간선을 한 번씩 보면서 한 단계 더 긴 경로의 정보를 전파하므로, 최악에도 n-1회면 유한 최단 거리 후보가 반영됩니다. 실제 간선 순서가 경로 방향과 맞으면 한 라운드에 여러 단계가 전달되어 더 빨리 안정될 수 있습니다.

각 라운드에서 changed를 false로 시작하고, 어떤 dist[v]도 낮아지지 않았다면 즉시 종료합니다. 이후 간선을 다시 봐도 더 낮출 값이 없기 때문입니다. 다만 early stop은 실제로 전체 edge pass가 끝난 뒤 판단해야 하며, 한 간선이 바뀌지 않았다고 라운드를 중단하면 안 됩니다.

예를 들어 S→A=4, A→B=3, B→C=-2를 이 순서로 읽으면 첫 라운드에 A=4, B=7, C=5가 연쇄 반영되고 두 번째 라운드가 변화 없이 끝납니다. 반대로 간선을 C, B, A 순서로 저장하면 여러 라운드가 필요합니다. dist[u] == INF인 edge는 건너뛰고, INF에 가중치를 더하지 않아야 합니다. n번째 추가 pass에서 갱신이 생기면 정상적인 유한 최단 거리 계산을 넘어 source-reachable negative cycle을 의심합니다.

두 배열을 쓰면 next = old에서만 읽으므로 역순 간선은 첫 라운드에 A만, 둘째에 B, 셋째에 C를 얻습니다. in-place는 같은 pass의 뒤쪽 간선이 앞쪽 갱신을 즉시 읽으므로 순방향 입력에서 한 라운드에 S-A-B-C가 모두 전달됩니다. 이것은 결과의 정확성 차이가 아니라 라운드 불변식과 조기 종료 시점을 구현이 어떻게 정의하는지의 차이입니다. 한 pass 중간에 changed가 잠깐 false인 간선이 나와도 뒤 간선에서 true가 될 수 있으므로 전체 pass가 끝나기 전 종료하면 안 됩니다. n번째 추가 pass의 갱신은 dist[u]가 유한할 때만 cycle 후보이며, 이후 cycle-to-target 도달성 전파를 별도로 합니다.