음수사이클이 있는 그래프 (다익스트라, 벨만포드, 플로이드와샬)

보통 음수가중치(가중치의 합이 음수값이 되는)를 갖는 간선이 있을 경우 다익스트라를 사용해도 되는 경우가 있고, 안되는 경우가 있다.

이 글에서의 다익스트라는 우선순위큐와 인접리스트를 사용한 다익스트라라고 가정한다.

아래의 그림을 봐보자.

 

출처 : https://8iggy.tistory.com/153

 

시작은 s에서 시작한다고 가정한다.

c와 d를 봐보자. c->d는 6이고 d->c는 -3이다. 이경우엔 음수간선이 있지만 음수사이클은 발생하지않는다.

먼저 c에대한 거리값은 5로 업데이트 될 것이다.

후에 c에서 d를 뽑아서 d에 대한 거리값을 11로 업데이트 후, d를 뽑았을 때 c로 가는 간선이 있기 때문에 c에대한 최솟값갱신을 시도해볼 것이다. 11-3을 하면 8인데, 이미 더 짧은 5로 저장되어있기 때문에 갱신될 일은 없고 여기서 그냥 끝이다.

이렇게 위와 같이 음수사이클이 없는 경우에는 음수간선이 있다고 하더라도 다익스트라로도 해를 구할 수 있다.

 

자 이제 다시 e와 f를 봐보자. e->f 는 3이고 f->e는 -6이다.

e에 대한 거리값은 2로 업데이트 되고, f는 5로 업데이트 될 것이다.

f를 뽑았을 때 e로가는 간선이 있기 때문에 e에 대한 최솟값 갱신을 시도해볼 것이다. 

시도를 했더니 5-6 => -1이기 때문에 최솟값갱신을 한다. (기존 2보다 더 작은값이니까)

최솟값갱신을 했기 때문에 e에대한 거리값은 -1이된다.

그리고 갱신을 했기 때문에 우선순위큐에 다시 넣었을 것이고, 나중에 다시 뽑아서 또 주변 노드들에 대해 최솟값갱신을 위해 시도를 할 것이다.

당연히 주변노드들에 대해서 최솟값갱신이 된다. 처음 2였을 때 갱신했던 값들이니, 현재 -1이라면 될 수 밖에 없다.

-1 + 3(e->f) -> -6(f->e)로 이제는 e에 대한 거리값이 -4가된다. 이후 무한반복...

 

이렇게 위와같인 음수사이클이 존재하는 경우, 다익스트라의 로직으로는 무한반복에 빠져버리기 때문에 사용할 수 없다.

이런 경우에는 벨만포드, SPFA를 사용한다. SPFA는 벨만포드를 좀 더 향상시킨 알고리즘이라고 한다.

 

플로이드와샬에서 업데이트를 수행 후, 각 정점에서 자기자신의 정점까지의 거리, 즉 dist[i][i]를 검사했을 때 0이 아닌 음수값이 나온다면 음수사이클이 존재하는 그래프라는걸 의미한다.