다익스트라(Dijkstra) 알고리즘: 최단경로 구하기

다익스트라(Dijkstra) 알고리즘: 최단경로 구하기

다익스트라 알고리즘이란?

다익스트라 알고리즘은 그래프 내의 가중치를 가진 정점들 간의 최단 경로를 찾는 알고리즘이다. 

 

이 알고리즘은 그리디 알고리즘으로 분류된다.

매 단계마다 현재까지 알려진 최단 경로와 가장 가까운 정점을 선택하여 최단 경로를 확장해나간다.

 

이 알고리즘은 한 번의 루프마다 하나의 정점을 처리하므로,

모든 정점들을 고려해야 할 경우 시간 복잡도가 O(V^2)가 될 수 있다.

 

가중치가 양수인 그래프에서 사용 가능하며, 음수 가중치가 있는 경우에는 정확한 결과를 보장하지 않는다.

 

작동과정

1. 출발 노드 설정

2. 출발 노드 기준으로 각 노드의 최소 비용 저장

3. 방문하지 않은 누드 중에서 가장 비용이 적은 노드 선택

4. 해당 노드를 거쳐서 특정한 노드로 가능 경우를 고려하여 최소 비용 갱신

5. 3~4번 반복

 

작동과정 예시

1. 그래프 준비

주어진 그래프에서 출발 정점을 'A'로 설정한다.

2. 거리 초기화

시작 정점에서 각 정점까지의 거리를 무한대로 설정하고, 시작 정점의 거리를 0으로 설정한다.

A: 0
B: ∞
C: ∞
D: ∞

 

3. 우선순위 큐 준비

시작 정점 'A'를 우선순위 큐에 넣는다. 큐의 내용은 (거리, 정점) 쌍으로 구성된다.

 [(0, 'A')]

 

🔮 우선순위 큐
- 큐(Queue)는 먼저 들어오는 데이터가 먼저 나가는 FIFO(First In First Out) 형식의 자료구조
- 우선순위 큐(Priority Queue)는 우선순위가 높은 데이터가 먼저 나가는 형태의 자료구조

 

< 반복 시작 >

4. 시작점 선택

우선순위 큐에서 ('A', 0)을 선택

5. 이웃 정점 검사

'A'의 이웃 정점은 'B'와 'C'입니다.
'B'까지의 거리: 0 + 2 = 2 (현재 거리 + A->B 가중치)
'C'까지의 거리: 0 + 1 = 1 (현재 거리 + A->C 가중치)

 

6. 반복 종료 조건 검사

큐는 아직 비어있지 않습니다.

 

7. 우선순위 큐에서 다음 정점 선택

('C', 1) 선택합니다.

 

8. 이웃 정점 검사

'C'의 이웃 정점은 'A', 'D'입니다.
'A'까지의 거리: 1 + 1 = 2 (현재 거리 + C->A 가중치)
'D'까지의 거리: 1 + 5 = 6 (현재 거리 + C->D 가중치)

 

9.반복 종료 조건 검사

큐는 아직 비어있지 않습니다.

10. 우선순위 큐에서 다음 정점 선택

('B', 2) 선택합니다.

 

11. 이웃 정점 검사

'B'의 이웃 정점은 'A', 'D'입니다. 이미 'A'까지의 거리가 2보다 짧기 때문에 건너뜁니다.
'D'까지의 거리: 2 + 3 = 5 (현재 거리 + B->D 가중치)

 

12. 반복 종료 조건 검사

큐는 아직 비어있지 않습니다.

13. 우선순위 큐에서 다음 정점 선택

('D', 5) 선택합니다.

 

14. 이웃 정점 검사

'D'의 이웃 정점은 'B'입니다. 이미 'B'까지의 거리가 5보다 짧기 때문에 건너뜁니다.

 

15. 반복 종료 조건 검사

큐가 비어있습니다.

< 반복 종료 >

 

16. 결과 반환