다익스트라 vs 플로이드 와샬 vs 벨만포드

그래프 문제를 끄적이다 보면 단골로 등장하는 알고리즘이다.

 

3개의 특징을 구분지어 보고자 한다.

 

1) 다익스트라 : 하나의 정점에서 다른 어떤 정점까지의 최단거리를 구할 때

2) 플로이드 와샬 : 모든 정점에서 다른 어떤 정점까지의 최단거리를 구할 때

3) 벨만포드 : 하나의 정점에서 다른 어떤 정점까지의 최단거리 구할 때

 

딱 보아도 플로이드 와샬이 시간 복잡도가 가장 크다.

다익스트라 O(V+E) > 벨만포드 O(VE) > 플로이드 와샬 O(V3제곱)

세 알고리즘은 장단점이 있다. 그러나 특수한 경우에는 특정한 알고리즘을 쓰는 것이 좋다.

 

Case 1. 하나의 정점에서 어떤 정점의 최단거리를 구할 때(일반적인 경우) => 다익스트라

Case 2. 음의 가중치가 존재하거나 음의 사이클을 검출 할 때 => 벨만포드

Case 3. 어떤 정점에서 어떤 정점의 최단거리를 동시에 구해야할 때 => 플로이드 와샬

 

*사실 다익스트라도 음의 가중치가 존재하는 경우에도 사용가능하다.

 

이는 다익스트라의 구현 방식의 문제다. 

만약 한번 방문한 정점을 다시 방문하지 못하도록 구현한다면 음의 가중치를 반영하지 못한다.

중복 방문을 허용한다면 음의 가중치를 반영할 수 있으나 만약 음의 사이클을 이룬다면 무한루프에 빠진다.

 

따라서 문제 상황을 정확히 분석하고 어떤 알고리즘이 가장 효율적일지 그리고 어떻게 구현할지 고민해야 한다.