2eesh   4년 전

벨만 포드 알고리즘에서

- D[i] = 시작점에서 i로 가는 최단 경로

1. 모든 간선 e(u,v,c)에 대해서 다음을 검사한다. (d[v] = Min(d[v], d[u] + c))

- 1번 과정을 총 N-1번 반복한다.

라고 알고 벨만 포드 알고리즘을 만들었습니다.

그런데 왜 d[i]배열을 채우기 위해서 N-1만큼 반복해서 돌아야하는지 이해가 안갑니다.

알려주세요 ㅠ

hesue615   3년 전

N - 1 만큼 도는 이유는 시작점에서 도착점 까지 최대 이용 할 수 있는 점의 개수를 의미합니다.

즉 정확한 값을 얻기 위해선 N - 1번까지 돌아야 즉 고려해야 하기 때문 입니다.

댓글을 작성하려면 로그인해야 합니다.