다익스트라 알고리즘과 플로이드 와샬 알고리즘에 대한 고찰

E개의 간선과 V개의 정점을 갖는 그래프가 있다고 가정하였을 때

 

다익스트라는 한 개의 정점에서 나머지 연결된 정점들까지의 거리를 O(ElogV)의 시간복잡도로 구할 수 있다.

 

시간복잡도에 대한 이유는 간선 만큼의 heap에 push가 발생한다. 그 횟수가 E이고 heap에 push하는데 걸리는 시간은 LogN 이므로 E개에 간선에 대해서 push가 발생하므로 LogN이 걸리는 push를 E번 수행 즉 E*logV 이다.

 

플로이드 와샬 알고리즘은 모든 정점에서 다른 모든 정점까지의 거리를 O(V^3)의 시간복잡도로 구할 수 있다. (왜냐하면 3중 for문 으로 구하니까) 그렇다면 모든 정점에서 다른 모든 정점까지의 거리를 구하려 할때 모든 정점에서 다익스트라를 사용한다면 시간복잡도는 V (모든 정점에 대해) * ElogV (다익스트라 수행) 이다.

 

그렇다면 시간복잡도를 비교하자면 O(V^3) 과 O(EVlogV) 인데 알고리즘을 조금이라도 접해보거나 수학적으로 사고해보면 LogN의 시간복잡도의 강력성에 대해 알 수 있을 것이다. 그렇다면 모든 정점에 대해 다익스트라를 수행하는 것이 항상 이득이라면 플로이드 와샬 알고리즘은 사장된 알고리즘이 아닐까?

 

 

정답은 아니다이다.

 

 

그 이유는 다음과 같다. 무향그래프에서 한 정점에서 다른 한 정점으로 가는 간선이 1개씩 있다고 하면 최대 간선의 개수는 N(N-1)/2개이고 유향 그래프의 경우 N(N-1)개이다.

 

즉 빅-오 표기법상으로는 N^2이므로 E의 최댓값은 V^2라는 이야기이다.

 

다익스트라 알고리즘을 모든 정점에 대한 수행한 경우 최악의 경우 O(V^3logV)가 되는 것이다. 그러므로 이러한 상황에서는 플로이드 와샬 알고리즘이 다익스트라 알고리즘 보다 빠르다는 얘기인 것이다. 게다가 다익스트라 알고리즘 자체적으로 매번 큰 수로 초기화된 배열을 만들어야 하고, 함수로 만들었다면 함수 호출과 같은 부가적인 시간 소모가 발생한다. 그에 반해 플로이드 와샬은 간결한 3중 for문으로 구하므로 이러한 애로사항도 없다.

 

플로이드 와샬 알고리즘의 가장 큰 단점은 시간복잡도라 생각한다. 솔직히 O(V^3)은 V가 100 내외 정도되는 경우의 문제들만 해결 할 수 있다. 그래도 위와 같은 상황에서는 굉장히 적합한 알고리즘이다.

 

아래문제는 위의 설명을 검증할 수 있는 문제이다.

다익스트라와 플로이드 와샬 두 방법 모두 풀 수 있는 문제이다.

https://www.acmicpc.net/problem/1719

1719번: 택배

 

맨 밑은 플로이드 와샬 위의 2개는 다익스트라를 이용한 풀이이다. 보는 바와 같이 메모리나 시간 부분에서 모두 플로이드 와샬이 더 좋은 성능을 보여준다.