[자율주행] Dijkstra algorithm이란 ? - 작동원리 및 예제

개요

Dijkstra알고리즘은 그래프에서 최단 경로를 찾기 위해 사용되는 알고리즘 중 하나입니다.
이 알고리즘은 Edsger Dijkstra에 의해 개발되었으며, 너비 우선 탐색(BFS)의 개념을 기반으로 합니다.
 
Dijkstra 알고리즘은 가중치가 있는 그래프에서 시작 노드로부터 다른 모든 노드까지의 최단 경로를 찾는 데 사용됩니다.
이 글에서는 Dijkstra 알고리즘의 작동 원리와 예제를 살펴보겠습니다.

Dijkstra 알고리즘 작동 원리

Dijkstra 알고리즘은 그래프의 각 노드에 대한 최단 경로 추정값을 유지하며, 이 추정값은 초기에는 무한대로 설정됩니다. 시작 노드의 최단 경로 추정값은 0으로 초기화됩니다. 알고리즘은 최단 경로가 확정되지 않은 노드 중에서 추정값이 가장 작은 노드를 선택하고, 해당 노드와 연결된 간선을 따라 이동합니다.
 
이동한 노드로부터 다른 노드까지의 경로의 길이를 계산하고, 현재까지 알려진 최단 경로보다 짧은 경로가 존재한다면 추정값을 갱신합니다. 이렇게 모든 노드에 대해 최단 경로를 갱신하면, 시작 노드로부터 모든 다른 노드까지의 최단 경로가 확정됩니다.
 
Dijkstra 알고리즘의 핵심 아이디어는 탐욕적인 선택 속성과 최적 부분 구조입니다. 탐욕적인 선택 속성은 매 단계마다 현재까지의 최단 경로 추정값이 가장 작은 노드를 선택하는 것을 의미합니다.
 
최적 부분 구조는 각 노드에 대한 최단 경로 추정값을 갱신할 때, 그 경로에 해당하는 노드들의 최단 경로도 갱신되는 것을 의미합니다.

Dijkstra 알고리즘 예제

이해를 돕기 위해 간단한 예제를 살펴보겠습니다. 다음과 같은 그래프가 있다고 가정해봅시다.
노드이웃 노드가중치

A	B	4
A	C	2
B	C	1
B	D	5
C	D	8
C	E	10
D	E	2
D	F	6
E	F	2

위 그래프에서 A를 시작 노드로 설정하고, 다른 모든 노드까지의 최단 경로를 찾아보겠습니다.

1. 초기화: 시작 노드 A의 최단 경로 추정값을 0으로 설정하고, 나머지 노드의 추정값을 무한대로 설정합니다.
2. A부터 출발하여 가장 가까운 노드 C를 선택합니다. A에서 C까지의 경로의 길이는 2입니다.
3. C를 경유하여 B로 이동할 때의 경로 길이는 3입니다. 따라서 B의 최단 경로 추정값을 3으로 갱신합니다.
4. B를 경유하여 D로 이동할 때의 경로 길이는 8입니다. 현재 D의 최단 경로 추정값은 무한대이므로, 8로 갱신합니다.
5. C를 경유하여 E로 이동할 때의 경로 길이는 10입니다. E의 최단 경로 추정값을 10으로 갱신합니다.
6. D를 경유하여 E로 이동할 때의 경로 길이는 10입니다. E의 최단 경로 추정값은 이미 10이므로 갱신하지 않습니다.
7. D를 경유하여 F로 이동할 때의 경로 길이는 14입니다. F의 최단 경로 추정값을 14로 갱신합니다.
8. E를 경유하여 F로 이동할 때의 경로 길이는 12입니다. F의 최단 경로 추정값을 12로 갱신합니다.

위 과정을 통해 시작 노드 A로부터 모든 다른 노드까지의 최단 경로를 찾을 수 있습니다.

결론

Dijkstra 알고리즘은 그래프에서 최단 경로를 찾기 위한 강력한 도구입니다.
이 알고리즘은 탐욕적인 선택과 최적 부분 구조의 원리에 기반하여 작동하며,
시작 노드로부터 다른 모든 노드까지의 최단 경로를 효율적으로 계산할 수 있습니다.
Dijkstra 알고리즘은 실생활에서 경로 탐색, 네트워크 라우팅 등 다양한 분야에서 활용됩니다.

---

자주 묻는 질문 (FAQs)

1. Dijkstra 알고리즘은 왜 중요한가요?
 
- Dijkstra 알고리즘은 그래프에서 최단 경로를 찾는 데 사용되는 중요한 알고리즘입니다. 다양한 분야에서 경로 탐색, 네트워크 라우팅 등 다양한 문제에 적용됩니다.
 
2. Dijkstra 알고리즘의 시간 복잡도는 어떻게 되나요?
 
- Dijkstra 알고리즘의 시간 복잡도는 O((V+E)logV)입니다. V는 노드의 수, E는 간선의 수를 나타냅니다.
 
3. Dijkstra 알고리즘과 벨만-포드 알고리즘의 차이는 무엇인가요?
 
- Dijkstra 알고리즘과 벨만-포드 알고리즘 모두 최단 경로를 찾는데 사용되지만,
Dijkstra 알고리즘은 양수 가중치 그래프에서만 사용할 수 있고, 벨만-포드 알고리즘은 음수 가중치 그래프에서도 사용할 수 있습니다.
 
4. Dijkstra알고리즘을 구현하는 데 어떤 자료구조를 사용해야 하나요?
 
- Dijkstra 알고리즘을 구현하는 데는 주로 우선순위 큐와 그래프 자료구조를 사용합니다.
우선순위 큐는 추정값이 가장 작은 노드를 효율적으로 선택하기 위해 사용됩니다.
 
5. Dijkstra 알고리즘의 한계는 무엇인가요?
 
- Dijkstra 알고리즘은 음수 가중치 그래프에서는 제대로 작동하지 않습니다.
또한, 그래프의 크기가 매우 크다면 계산 시간이 오래 걸릴 수 있습니다.