다익스트라 알고리즘(Dijkstra's Algorithm) 정의 동작방식 복잡도 사용예시

안녕하세요, 이번 포스팅에서는 자주 쓰이는 소프트웨어 알고리즘 중 하나인 다익스트라에 대해 알아보겠습니다.

 

 

<정의>

다익스트라 알고리즘(Dijkstra's Algorithm)은 가중치가 있는 그래프에서 시작 정점으로부터 다른 모든 정점까지의 최단 경로를 찾는 알고리즘입니다. 이 알고리즘은 음의 가중치를 허용하지 않으며, 주로 길 찾기 문제 등에 사용됩니다.

 

 

<동작방식>

1. 그래프 초기화: 시작 정점을 기준으로 모든 정점까지의 거리를 무한대로 설정하고, 시작 정점의 거리를 0으로 설정합니다.

2. 우선순위 큐(최소 힙) 초기화: 시작 정점을 우선순위 큐에 넣습니다. 이때, 시작 정점의 거리를 우선순위 큐의 우선순위로 설정합니다.

3. 최단 경로 탐색: 우선순위 큐에서 가장 거리가 짧은 정점을 꺼내고, 해당 정점과 연결된 모든 인접한 정점들에 대해 다음을 수행합니다.
  - 시작 정점에서 해당 정점까지의 거리를 계산합니다. (현재까지의 최단 거리와 간선의 가중치를 더한 값)
  - 계산된 거리가 해당 정점까지의 현재 최단 거리보다 작다면, 해당 정점의 최단 거리를 업데이트하고, 우선순위 큐에 넣습니다.

 

4. 우선순위 큐가 빌 때까지 3단계를 반복합니다.

5. 알고리즘이 종료되면, 시작 정점으로부터 모든 다른 정점까지의 최단 거리가 구해집니다.

 

반응형

 

<복잡도>

다익스트라 알고리즘의 시간 복잡도는 우선순위 큐의 크기에 따라 달라지며, 주로 우선순위 큐를 사용하는 경우 O((E + V) log V)의 시간 복잡도를 가지게 됩니다. 여기서 E는 간선의 수, V는 정점의 수를 나타냅니다.

 

 

<사용 예시>

다익스트라 알고리즘은 최단 경로 문제를 풀 때 사용되며, 네트워크 라우팅, GPS 기반 길 찾기, 인터넷 라우터 등 다양한 분야에서 활용됩니다. 다익스트라 알고리즘을 통해 최단 경로를 찾을 수 있다면, 그래프 내에서 효율적인 길을 찾거나 비용을 최소화하는 문제를 풀 수 있습니다.