정확히 무엇을 물어보시는지 모르겠지만 설명드리자면,
밸만포드 알고리즘의 기본 아이디어는
최단 거리 이동은 무조건 (정점 개수 - 1)번 만에 일어난 다는 것에서 시작합니다.
그래서 음의 사이클 판별은 v-1번 이후에서 값의 update가 있다 없다고 판별되는 것이죠.
말씀하신 것처럼 가중치가 1이라면
음의 사이클이 없는 그래프라면 v-1번의 update 안에 이미 그것을 포함시켰을 겁니다.
쉽게 생각하시면 v-1번의 update 이후에는 무조건 모든 점의 최단거리는 setting되어있고 (음의 사이클이 없다면 )
그래서 한 번 더 update를 시도해보고 update가 이루어진다면 음의 사이클이 존재한다고 판단하는 거죠.
제가 댓글 의미를 정확히 파악하지 못하겠어서 이 글을 읽어보시고 다시 질문해주신다면 답변드리겠습니다.

js0304 1년 전
안녕하세요,
간선의 가중치가 1이어도 음의 사이클이 존재하지 않지만 v-1번째 탐색까지 업데이트가 이루어지는 경우가 아닌가요? 제가 놓치는 부분이 있는지 여쭤봅니다.