Bellman-Ford

음수 간선은 V-1번 완화하고, 한 번 더 검사한다

Bellman-Ford는 모든 간선을 반복해서 보고, 마지막 추가 완화 여부로 음수 사이클을 잡는다.

초기화start = 0, 나머지 거리는 INF

V-1회 반복모든 간선 u→v에 대해 완화

추가 1회또 줄어들면 음수 사이클

라운드	확인하는 것	정상 신호	오답 신호
1..V-1	모든 간선 완화	도달 가능한 최단거리 감소	한 간선만 보고 라운드 종료
도달성	`dist[u] != INF`	도달 가능한 정점에서만 전파	INF + weight 계산
V번째	추가 완화 가능 여부	변화 없으면 음수 사이클 없음	변화 있으면 음수 사이클

핵심: 음수 간선 자체가 문제가 아니라, V번째 완화가 남아 있는지가 음수 사이클의 증거다.