[알고리즘] 다익스트라(Dijkstra) - 최단 경로와 동작 원리

다익스트라 (Dijkstra) 알고리즘은 시작 정점에서 다른 모든 정점까지의 최단거리를 구하는 알고리즘이다.
 
예를 들어 지도 어플에서 현재 위치에서 목적지까지 가장 빠른 길을 찾거나
네트워크에서 데이터가 이동하는 최적 경로를 찾을 때 사용된다.
 
다익스트라 알고리즘은 그래프의 가중치를 기준으로 최단 거리를 계산하기 때문에 가중 그래프에서 많이 사용된다.

※ 단, 다익스트라 알고리즘은 음수 가중치가 있는 그래프에서는 사용할 수 없다.

---

1. 최단 경로 알고리즘(Shortest Path Algorithm)

최단 경로 알고리즘은 그래프에서 특정 정점에서 다른 정점까지 이동할 때 가장 적은 비용이 드는 경로를 찾는 알고리즘이다.
그래프의 가중치를 기준으로 최단 경로를 판단하기 때문에
거리, 시간, 비용 등 어떤 값을 가중치로 설정하는지에 따라 최단 경로의 기준이 달라질 수 있다.

 

💡 최단거리란?

최단거리는 시작 정점에서 목표 정점까지 이동할 때 필요한 비용이 가장 작은 경로를 의미한다.
BFS는 모든 이동 비용이 동일한 그래프에서 최단 경로를 찾을 때 사용하고,
다익스트라는 각 이동마다 다른 비용을 가진 가중 그래프에서 최단 경로를 찾을 때 사용한다.

• 이동 비용이 가장 적은 경로
• 이동 시간이 가장 짧은 경로
• 거리의 합이 가장 작은 경로

❓ 왜 음수 간선을 사용할 수 없을까?

다익스트라는 현재 가장 짧다고 판단한 값을 스스로 믿고 다음으로 넘어가는 특성이 있다.
그런데 음수 간선이 있을 경우엔 더 짧은 경로가 생길수도 있어
이미 확정했다고 생각한 값이 바뀌는 오류가 생긴다.
그렇기 때문에 다익스트라는 음수 간선이 있는 그래프에는 적합하지 않으며
음수 간선이 있을땐 다른 최단거리 알고리즘을 사용해주어야한다.

※ 음수 간선이 있을 때 : 밸만-포드 알고리즘, 플로이드-위셜 알고리즘등을 사용할 수 있다.

---

2. 다익스트라 알고리즘 동작 원리

다익스트라 알고리즘은 시작 정점에서 각 정점까지의 거리를 저장하는 배열을 사용한다.
처음엔 모든 거리를 매우 큰 값으로 설정한 뒤 시작점의 거리는 0으로 설정한다.
그리고 난 뒤 현재까지 가장 거리가 짧은 정점을 하나 꺼내
현재 정점을 거쳐 다른 정점으로 가는 경로가 더 짧다면 값을 갱신한다.
위 과정을 반복하여 시작에서 모든 정점까지의 최단 거리를 구한다.

1. 그래프와 거리 배열을 준비한다.
2. 모든 거리를 무한대로 초기화하고 시작점의 거리를 0으로 설정한다.
3. 가장 거리가 짧은 정점을 선택하여 연결된 정점들의 거리를 확인한다.
4. 더 짧은 경로가 있을 경우 거리값을 갱신한다.
5. 모든 정점에 대해 과정을 반복하여 최단 거리를 구한다.

❓ 왜 처음 거리를 무한대(∞)로 설정할까?

다익스트라 알고리즘은 기존 거리와 새로 찾은 거리를 비교하면서 더 작은 값으로 갱신하는 방식이다.
처음에는 각 정점까지의 거리를 알 수 없기 때문에 가장 큰 값인 무한대(∞)로 설정한다.

시작 : A

A = 0
B = ∞
C = ∞
D = ∞

시작 정점 A는 자기 자신까지 이동 비용이 없기 때문에 0으로 설정하고,
다른 정점들은 이후 더 짧은 경로를 찾을 때마다 값이 갱신된다.

---

3. BFS와 다익스트라 알고리즘 차이

BFS는 얼마나 적은 횟수로 이동하는가를 구하는 알고리즘이고
다익스트라는 얼마나 적은 비용으로 이동하는가를 구하는 알고리즘이다.

구분	BFS	다익스트라
목적	최소 이동 횟수	최소 비용
가중치	동일한 비용	서로 다른 비용 가능
탐색 기준	먼저 발견한 정점	현재 비용이 가장 적은 정점
자료구조	Queue	Priority Queue