정점의 갯수가 N이라고 하면 N - 1회만큼을 최단거리 갱신을 위해 반복하고, 나머지 1번을 통해서 음의 순환을 체크하는데요.

N - 1회를 하는 이유는 순환 없이 도착지를 제외한 모든 정점을 거쳐서 갈 수 있는 최단 거리에 대한 가능성으로 수행한다고 알게 됐습니다.

이 지점이 이해가 안 되는 부분인데요. 주어진 모든 간선에 대한 탐색을 N - 1회나 반복할 필요가 있는지 잘 모르겠습니다.

N이 3 이상이더라도 정점이 모두 양수거나 혹은 음의 순환이 일어나지 않는 음의 정점이 있다고 하면 1회만 수행하더라도 간선에 대한 갱신이 가능하고 2회 부터는 더 이상의 갱신이 일어나지 않는다고 보는데 왜 이렇게 하면 안되는 것인지 궁금합니다. 연습장에 그래프를 몇개 만들어서 돌려봐도 2회 부터는 갱신이 일어나지 않았습니다.

현재까지는 2회부터는 더 이상의 최단 거리 갱신이 일어나지 않는다고 생각하는데, 제가 이 부분에 대해서 제대로 이해하지 못하고 있는 듯 합니다.

왜 N - 1회 만큼 최단 거리 갱신을 수행해야 하는지 알고 싶습니다. 그리고 추가적으로 가능하다면 N - 1회씩 돌려야 최단 거리 갱신이 가능한 그래프에 대한 예시도 알려주신다면 정말 감사하겠습니다.