다익스트라는 한 노드에서 모든 노드에 대한 거리를, 플로이드 워셜은 모든 노드에서 모든 노드에 대한 거리를 찾는 알고리즘이다.
상당히 유사한 이 둘을 비교해보려 한다.
특수한 예외가 없는 경우, “모든 노드에서 모든 노드에 대한 거리를 찾는” 방법의 경우는 두 가지이다.
이 때 다익스트라는 heapq를 쓸 경우 O(N * log N)이기 때문에,
다익스트라 : O(N^2 * log N) (모든 노드 N개에 대하여 다익스트라를 시행해야하기 때문에 N이 추가로 곱해짐.) 플로이드워셜: O(N^3)
으로 둘 다 가능한 경우에는 웬만해선 다익스트라가 플로이드 워셜보다 시간복잡도 면에서 유리하다.
항상 저런 상황만 있다면 당연히 다익스트라를 쓰면 되는데, 그래프에 “음수 사이클”이 있는 경우에는 다익스트라를 사용할 수 없다. ! 음수 간선이 있다고 다익스트라를 아예 못쓰는 것은 아니다. 음수 사이클의 존재 여부가 중요하다.
이 경우에 플로이드 워셜 또한 정답 보장할 수 없다는 것은 마찬가지지만, 플로이드 워셜은 음수 사이클의 존재 여부를 확인할 수 있다. 알고리즘 시행 결과 자기 자신에게 돌아오는 데 드는 가중치, 즉 배열의 대각선 값이 0보다 작은 경우가 있다면 음수 사이클이 존재하는 것.
그럼 음수 사이클을 확인할 수 있는 또 다른 알고리즘인 벨만-포드 알고리즘과도 비교해볼 수 있겠다. 벨만포드는 음수 사이클 판별이 가능한 다익스트라라고 보는 것이 더 옳아보이는데, 벨만포드 또한 기본적으로는 “단일 - 전체 대상”의 거리 판별 알고리즘이기 때문이다.
그래서 벨만포드도 모든 거리에 대해서 사용하려면 시간복잡도에 N이 곱해져야하는가 싶지만, 일반적으로 벨만포드를 루프 판별용으로 사용하는 경우, 시작 노드는 어느 것이 되든 상관 없기 때문에 N^2로 보는 것이 옳아보인다.
정리하자면,
| 적용대상 | 음수 사이클 판별 | 모든노드(N) | 모든노드(V,E) | 단일노드(N) | 단일노드(V,E) | |
|---|---|---|---|---|---|---|
| 다익스트라 | 단일-전체 | X | N^2 * log N | VE log V | N log N | E log V |
| 벨만-포드 | 단일-전체 | O | N^3 | V^2 * E | N^2 | VE |
| 플로이드-워셜 | 전체-전체 | O | N^3 | V^3 | - | - |
이렇게 보면 플로이드-워셜이 굉장히 열등해보이는데, 저것만 쓸 수 있는 상황이 있을까?
만약 방향성 그래프에서 일방 통행에 의해 그래프 상에서 두 지역이 분리되는 경우에는, 벨만-포드에서 시작 노드를 잘못 고르면 음수 사이클의 존재도 판별할 수 없다. 음수 사이클이 존재하는 것도 특수한데, 이 경우는 더더욱 특수하다. ← 그런데 이런 경우가 가능할까? 나중에 한번 찾아보든가, 문제를 풀면서 마주해봐야겠다. 적절한 예시를 찾으면 그림으로 올리기.