주의 : 해당 문제 질문 게시판의 풀이 및 논란 완전 정리합니다. 라는 글에 대한 보충 설명을 스스로 이해할 수 있도록 정리한 글입니다.
이 문제에서 핵심 의문은 다음 2가지였다.
- 시작 정점이 어디인가?
- 연결 그래프 여부가 왜 표시되어 있지 않은가?
결론적으로 말하면 다음과 같다.
시작 정점의 여부는 필요하지 않다. 또한, 단절된 그래프가 주어지는 경우도 생각해야 한다. 그리고 이 두 부분은 의도된 것이다.
코드 1
INF = 2000000000
모든 dist[v] = INF
dist[1] = 0
N-1번 반복:
모든 v에 대해:
모든 간선에 대해 최단거리 갱신
모든 v에 대해:
모든 간선에 대해 최단거리 갱신
갱신이 한 번이라도 일어났으면 true
===
코드 2
INF = 2000000000
모든 dist[v] = INF
dist[1] = 0
N-1번 반복:
dist[v] != INF인 모든 v에 대해:
모든 간선에 대해 최단거리 갱신
dist[v] != INF인 모든 v에 대해:
모든 간선에 대해 최단거리 갱신
갱신이 한 번이라도 일어났으면 true코드1은 이번 문제가 요구하는 코드, 코드2는 원래 벨만포드 알고리즘이다.
Case 1에 해당하는 예시 그래프가 위와 같이 주어졌다고 생각해보자. 이때, 위 그래프는 전체 그래프 중 시작 정점에서 도달할 수 없는 단절된 그래프를 나타낸 것이다.
코드 1의 경우를 생각해보자.
Case 1. 정점이 2개이므로 밸만 포드 알고리즘은 모든 간선에 대해 1회의 Relaxation을 수행한다. 그렇다면 오른쪽 정점은 INF-4의 값을 가지게 된다. 이후에 더 이상 Relaxation 가능한 간선은 존재하지 않는다. 따라서 음수 사이클이 없다고 판단한다. 이는 옳은 판단이다.
Case 2. 이제 오른쪽 → 왼쪽 -5 간선이 있다고 생각해보자. 정점이 2개이므로 밸만 포드 알고리즘은 모든 간선에 대해 1회의 Relaxation을 수행한다. 그렇다면 오른쪽 정점은 INF-4의 값을 가지게 된다. 왼쪽 정점 역시 INF-5의 값을 가지게 된다. 여전히 Relaxation 가능한 간선이 존재하므로 음수 사이클이 존재한다고 판단한다. 그리고 이는 옳은 판단이다.
단절된 그래프임에도, 두 case에 대해서 코드1은 음수 사이클의 존재 여부를 정확히 판단해 내고 있는 것을 볼 수 있다.
원래 벨만포드 알고리즘은 INF가 숫자가 아닌 (무한대라는) 상태를 나타낸다. 다시 말해, 원래의 벨만 포드 알고리즘은 INF-4로 오른쪽 정점의 값을 갱신하지 않는다. 코드1이 이처럼 동작하는 이유는, 구현 상 INF가 어떠한 숫자로 지정되어 있기 때문이다. 그렇기 때문에, 코드1을 파이썬의 float('inf')를 이용해 구현한다면 틀린 코드가 된다. 파이썬에서 float('inf') - 4는 여전히 float('inf')로 취급하기 때문이다. 따라서 아예 처음부터 Relxation이 불가능하다고 판단해 아무것도 갱신하지 않는 코드로 작동한다.
사실 코드1에서 시작 정점 초기화 조건(dist[1] = 0)은 아예 존재하지 않아도 된다. 어차피 도달할 수 없는 그래프이기 때문이다. 또는 다음과 같이도 생각할 수 있다. '모든 정점이 INF인 그래프에서 임의의 정점을 시작 정점으로 하여 벨만 포드 알고리즘을 수행한다.' 그래도 알고리즘은 음수 사이클을 성공적으로 찾아낸다는 것을 우리는 이미 위에서 보았다.
단순히 음수 사이클을 찾고 싶다면, 시작 정점은 고려하지 않아도 된다!
코드 2의 경우를 생각해보자.
- 애초에 시작 정점에서 도달하는 것이 불가능하다.
- 간선의 시작 정점 (u→v 애서 u)이 INF라면 Relaxation을 수행하지 않는다.
이 두가지 특성때문에, 단절된 그래프에서는 무조건 음수 사이클이 없다고 동작함을 알 수 있을 것이다.
