아마 INF일 때 건너 뛰는 코드(24줄, 34줄) 부분을 지우면 INF로 전부 초기화해도 정답처리 될 겁니다.
전체 그래프에서 (출발지와는 상관 없이) 음의 사이클이 존재하는지를 판별하는 문젠데, dist값을 0(출발지), INF(나머지)로 초기화하고 벨만 포드를 돌리면 출발 노드와 연결된 그래프 속에 존재하는 음의 사이클만 확인할 수 있고, 다른 곳은 확인할 수 없기 때문에 오답처리가 됩니다.
INF가 아니라 -1로 초기화했을 때 정답이 되는 이유는 다음과 같습니다.
노드가 1부터 n까지 있고, 초기 dist값을 a1, a2 ... an 으로 설정하면, 1~n 노드와 가중치가 a1, a2 ... an인 간선으로 연결된 "가상의 0번 노드"를 출발지로 해서 벨만 포드를 돌리는 것과 같아지게 됩니다. 여기서 모든 dist 값을 -1로 둔다면, 출발 노드인 0번 노드와 1~n 노드가 가중치가 -1인 간선으로 모두 연결되는 것과 같습니다. 모두 연결된 그래프가 되기 때문에 기존 그래프에 존재하는 모든 음의 사이클을 확인할 수 있게됩니다.
때문에 -1이 아니라 INF보다 적당하게 작은 아무값으로 초기화해도 결과에 영향을 주지 않습니다.
INF를 초기값으로 설정하면, 24줄, 34줄에서 dist값 갱신을 막아버리기 때문에 음의 사이클을 판별할 수 없게 되나, 해당 줄을 지워버리면 마찬가지로 모든 위치에서 음의 사이클을 확인할 수 있게 됩니다.
blou888 2년 전
이번에 처음으로 벨만-포드 알고리즘을 접했는데, 아직 벨만 포드를 이해를 못했습니다..
제가 원래 짠 코드는 1이라는 정점에서 시작하는 것 같은데,
다른 사람의 코드를 참고해서 봤는데, memset을 넣은 코드가 통과를 받고, memset을 넣지 않으면 틀렸습니다를 받습니다.
dist에 INF가 들어가는 것과, -1이 들어가면 결과값이 다른 것 아닌가요??
코딩의 고수님들 설명좀 부탁드리겠습니다...