[자료구조 및 알고리즘] 그래프에서 음의 사이클 구하기 (벨만 포드 알고리즘, 플로이드 워셜 알고리즘)

그래프에서 음의 사이클 구하기

벨만 포드 알고리즘을 이용하는 것과 플로이드 워셜 알고리즘을 이용하면 그래프에서 음의 사이클을 찾아낼 수 있다.

 

플로이드 워셜 알고리즘을 이용한 방법

mp를 그래프라고 할 때, 플로이드 워셜 알고리즘에서 사이클의 존재 여부는 mp[i][i] 값을 통해서 확인할 수 있다.

 

• 플로이드 워셜 알고리즘은 모든 정점 쌍 간의 최단 경로를 구하기 위해 각 정점 i에서 j로 가는 최단 경로를 mp[i][j]에 저장하게 된다.
• 사이클이 없는 경우라면, 어떤 정점에서든 자신으로 돌아오는 경로가 존재하지 않으므로 mp[i][i]는 초기화된 값인 INF를 유지하게 된다.
• 반면, 사이클이 존재하는 경우 해당 경로의 길이를 갱신하게 되어 mp[i][i] (자기 자신에게로 돌아오는 경로)가 INF가 아닌 값으로 바뀌게 된다.

mp[i][i] != INF 인 경우, 정점 i에서 i로 돌아오는 경로가 있음을 의미하며, 사이클이 존재한다고 볼 수 있다. 이 방법은 특히 음수 사이클을 판별할 떄도 사용할 수 있다. mp[i][i] < 0인 경우, 음수 가중치 사이클이 존재함을 의미한다. 따라서 mp[i][i]가 INF가 아닌 값을 가질 때 사이클이 있다고 판별할 수 있다.

 

벨만 포드 알고리즘을 이용한 방법

벨만 포드 알고리즘은 음수 가중치가 있는 그래프에서도 최단 경로를 구할 수 있는 알고리즘이다. 음수 사이클이 없는 경우에도 사용할 수 있으나, 음수 사이클이 있으면 최단 거리를 판별할 수 없으므로 이를 판별하는 과정이 있다. 이 과정에서 음수 사이클을 판별할 수 있다.

 

• 모든 간선을 V - 1번 반복하며 확인한다. (V는 정점의 수, E는 간선의 수)
• 매 반복마다 모든 간선 (u, v, weight)에 대해, dist[u] + weight < dist[v]라면 dist[v]를 갱신한다.
• V - 1번 반복하는 이유는 최단 경로가 최대 V - 1개의 간선을 가질 수 있기 떄문이다.
• V - 1번 반복이 끝난 후, 한 번 더 모든 간선을 확인한다.
• 만약 이 과정에서 거리가 더 줄어드는 정점이 있다면, 음수 사이클이 존재함을 의미한다.