Dijkstra & Floyd-Warshall

 

❒ Description

---

알고리즘 문제를 풀면서 Dijkstra 알고리즘과 Floyd-Warshall 알고리즘을 학습했다.

이제 이 두 알고리즘의 차이를 정리해보자.

 

 

 

 

 

❒ 차이점

---

다익스트라(Dijkstra) 알고리즘과 플로이드-워샬(Floyd-Warshall) 알고리즘은 모두 최단 경로를 찾는

알고리즘이지만, 두 알고리즘 간에는 여러 차이가 있다. 

 

1. 적용 대상 및 문제 유형

다익스트라 알고리즘은 

• 하나의 시작점에서 모든 정점으로의 최단 경로를 찾는데 사용된다.
• 단일 출발점 최단 경로 문제에 적합하다.
• 주로 가중치가 양수인 그래프에 사용된다.
• 그래프가 희소(Sparse)할 때 효율적이다. (간선의 수가 적을 때)

 

반면에 플로이드-워샬 알고리즘은

• 모든 정점 간의 최단 경로를 찾는데 사용된다.
• 모든 정점에서 다른 모든 정점으로 가는 최단 경로를 구하는 문제에 적합하다.
• 가중치가 음수인 간선도 허용되지만, 음수 사이클이 있는 경우 올바른 결과를 보장하지 못한다.

 

2.  시간복잡도

다익스트라 알고리즘은

• 우선순위 큐를 사용하면 O((V+E)logV)의 시간복잡도를 갖는다.
  • V : 정점의 수
  • E : 간선의 수
  • 간선의 수 가 적으면 (V+E)항이 V에 가까워 진다. 이때는 O(VlogV)가 될 수도 있다.

 

반면에 플로이드-워샬 알고리즘은

• 모든 정점과 모든 정점 간의 경로를 계산하기 때문에 O(V³)의 시간 복잡도를 갖는다.
  • K, I, J 이렇게 3개의 변수를 선언하고 작업을 해야한다.

 

3. 알고리즘 특성

다익스트라 알고리즘은

• Greedy(탐욕적) 방법을 사용하여 각 단계에서 최단 경로를 확정해 나가는 방식이다.
• 출발점에서 부터 다른 정점까지의 경로를 점진적으로 계산한다.
• 가중치가 음수인 그래프에서는 올바르게 동작하지 않는다.

 

반면에 플로이드-워샬 알고리즘은

• Dynamic Programming(동적 계획법)을 사용하여 그래프의 모든 정점 쌍에 대한 최단 경로를 계산한다.
• 한 번의 수행으로 모든 정점  간의 최단 경로를 구할 수 있다.

 

4. 메모리 사용량

다익스트라 알고리즘은

• 주로 단일 출발점에서 다른 정점으로의 최단 경로를 찾으므로, 상대적으로 메모리 사용량이 적다.

 

반면에 플로이드-워샬 알고리즘은

• 모든 정점 쌍에 대해 최단 경로를 저장해야 하므로, O(V²)의 메모리 사용량(= 공간 복잡도)을 갖는다.

 

 

 

 

---