Posted by 다익스트라 알고리즘(Dijkstra’s Algorithm)은 가중치가 있는 그래프에서 최단 경로를 찾는 가장 널리 사용되는 알고리즘 중 하나이다.
이 알고리즘은 네트워크 라우팅, 지도 서비스, GPS 경로 탐색 등 다양한 분야에서 핵심적인 역할을 한다. 이번 포스트에서는 다익스트라 알고리즘의 개념과 원리부터 실제로 어떻게 구현하는지까지 자세히 알아보자.
다익스트라 알고리즘(Dijkstra’s Algorithm)이란?
다익스트라 알고리즘은 비음수 가중치(양수로만 가중치가 구성되어 있는 경우)가 있는 그래프에서 한 노드에서 다른 모든 노드로 가는 최단 경로를 찾는 알고리즘이다. 시작 노드에서 다른 노드로 가는 경로들 중에서 비용(가중치)이 가장 적은 경로를 선택하며, 이 과정에서 우선순위 큐를 활용해 효율적인 탐색을 수행한다.
알고리즘의 주요 특징
- 단일 출발점 최단 경로: 출발점에서 모든 노드로 가는 최단 경로를 계산한다.
- 비음수 가중치: 그래프의 간선(Edge)의 가중치는 0 이상이어야 한다. 음수 가중치가 있을 경우, 다익스트라 알고리즘은 올바른 경로를 계산하지 못한다.
- 탐욕적 알고리즘: 현재 시점에서 가장 최적의 선택을 하여 결과적으로 최적의 해를 찾는다.
다익스트라 알고리즘의 동작 원리
다익스트라 알고리즘은 다음과 같은 순서로 동작한다.
- 초기화: 출발 노드의 거리는 0으로 설정하고, 다른 모든 노드의 거리는 무한대(∞, inf)로 설정한다. 그리고 출발 노드를 방문 처리하고, 현재 거리를 기준으로 탐색을 시작한다.
- 가장 가까운 노드 선택: 아직 방문하지 않은 노드들 중에서 가장 짧은 거리를 가진 노드를 선택한다. 초기에는 출발 노드가 선택된다.
- 인접한 노드 업데이트: 선택된 노드의 인접 노드로 가는 경로를 확인하고, 그 경로의 거리가 현재 알고 있는 거리보다 짧으면 거리를 업데이트한다.
- 반복: 모든 노드를 방문할 때까지 이 과정을 반복한다.
이 과정은 우선순위 큐(Priority Queue)를 사용하여 가장 가까운 노드를 효율적으로 선택하는 방식으로 진행된다.
예시: 간단한 그래프에서 다익스트라 알고리즘 적용
다음 그래프를 예시로 들어 다익스트라 알고리즘이 어떻게 동작하는지 살펴보자.
A --1--> B --3--> C | | | 4 2 1 | | | D --5--> E --1--> F
여기서 각 간선에 적힌 숫자는 가중치(비용)를 의미한다. A에서 F까지의 최단 경로를 구해보면, 다익스트라 알고리즘은 다음과 같은 순서로 동작한다.
- 시작 노드 A 선택: A에서 출발하고, A의 인접 노드인 B(1)와 D(4)의 거리를 기록한다.
- B 노드 선택: 현재 가장 짧은 경로인 B(1)를 선택하고, B의 인접 노드인 C(3)와 E(2)의 거리를 업데이트한다.
- E 노드 선택: 다음으로 가장 짧은 경로인 E(2)를 선택하고, E의 인접 노드인 F(1)를 업데이트한다.
- F 노드 선택: F까지 도달했으므로, 최단 경로는
A → B → E → F이며, 이 경로의 총 가중치는1 + 2 + 1 = 4이다.
다익스트라 알고리즘의 Python 구현
이제 Python으로 다익스트라 알고리즘을 구현하는 방법을 살펴보자. 이를 위해 우선순위 큐를 사용할 것이며, Python의 heapq 모듈을 이용해 효율적인 큐 동작을 구현할 수 있다.
import heapq
# 그래프를 인접 리스트로 표현
graph = {
'A': {'B': 1, 'D': 4},
'B': {'A': 1, 'C': 3, 'E': 2},
'C': {'B': 3, 'F': 1},
'D': {'A': 4, 'E': 5},
'E': {'B': 2, 'D': 5, 'F': 1},
'F': {'C': 1, 'E': 1}
}
# 다익스트라 알고리즘 함수 (시작점과 도착점 지정)
def dijkstra(graph, start, end):
distances = {node: float('inf') for node in graph} # 시작 노드 이외의 거리는 무한대로 설정
distances[start] = 0 # 시작 노드의 거리는 0
priority_queue = [(0, start)] # (거리, 노드) 형태로 큐 초기화
previous_nodes = {node: None for node in graph} # 경로 추적을 위한 이전 노드 기록
while priority_queue:
current_distance, current_node = heapq.heappop(priority_queue)
# 현재 노드가 도착 노드라면 종료
if current_node == end:
break
# 이미 처리된 노드라면 무시
if current_distance > distances[current_node]:
continue
# 현재 노드의 인접 노드들에 대해 거리 계산
for neighbor, weight in graph[current_node].items():
distance = current_distance + weight
# 더 짧은 경로를 찾았다면 거리 업데이트
if distance < distances[neighbor]:
distances[neighbor] = distance
previous_nodes[neighbor] = current_node # 이전 노드를 기록
heapq.heappush(priority_queue, (distance, neighbor))
# 도착 노드까지의 최단 경로 추적
path = []
current = end
while current is not None:
path.append(current)
current = previous_nodes[current]
path = path[::-1] # 경로를 역순으로 만들어서 올바른 순서로 출력
return distances[end], path
# 다익스트라 알고리즘 실행 (시작점 'A', 도착점 'F')
start_node = 'A'
end_node = 'F'
distance, path = dijkstra(graph, start_node, end_node)
# 결과 출력
print(f"Shortest distance from {start_node} to {end_node}: {distance}")
print(f"Path: {' -> '.join(path)}")
코드 설명
- graph: 그래프를 인접 리스트로 표현한 것이다. 각 노드가 인접 노드들과의 가중치를 딕셔너리 형태로 저장한다.
- dijkstra 함수
- start와 end: 시작점과 도착점을 함수의 인자로 받아, 출발점에서 도착점까지의 최단 경로를 구한다.
- distances: 각 노드까지의 최단 거리를 저장하는 딕셔너리이다. 시작점의 거리는 0으로 설정되고, 나머지는 무한대(∞, inf)로 설정된다.
- previous_nodes: 경로 추적을 위해 각 노드의 이전 노드를 기록하는 딕셔너리이다. 이를 통해 최종 경로를 추적할 수 있다.
- priority_queue: 현재까지의 거리를 기준으로 가장 짧은 거리를 가진 노드를 탐색하는 데 사용되는 우선순위 큐이다.
- while 루프: 큐에서 노드를 꺼내 인접 노드들을 탐색하며, 더 짧은 경로를 발견하면 경로와 거리를 업데이트한다. 도착 노드에 도착하면 반복을 종료한다.
- 경로 추적 (path):
previous_nodes딕셔너리를 활용해 도착점에서부터 시작점까지의 경로를 추적한 후, 역순으로 정렬해 최종 경로를 구한다. - 결과: 최단 거리와 경로를 출력한다. 예를 들어, ‘A’에서 ‘F’까지의 경로는
A -> B -> E -> F이며, 그 경로의 총 가중치(거리)는 4이다.
다익스트라 알고리즘의 한계
다익스트라 알고리즘은 비음수 가중치에 대해서만 올바르게 동작한다. 만약 그래프에 음수 가중치가 포함되어 있다면, 벨만-포드(Bellman-Ford) 알고리즘을 사용하는 것이 더 적합하다. 또한, 매우 큰 그래프의 경우 메모리 사용량이 많아질 수 있으므로 적절한 자료 구조를 선택하는 것이 중요하다.
다익스트라 알고리즘의 실생활 활용 사례
다익스트라 알고리즘은 다음과 같은 실제 문제에서 사용된다.
- 네트워크 라우팅: 네트워크 내에서 가장 빠른 경로를 찾는 데 사용된다.
- GPS 네비게이션: A에서 B까지의 최단 경로를 계산하는 지도 서비스에 활용된다.
- 게임 AI: 게임 캐릭터가 목적지로 이동하는 경로를 계산하는 데 사용된다.
결론
다익스트라 알고리즘은 그래프에서 최단 경로를 찾는 매우 강력한 도구이다. 우선순위 큐를 사용하여 효율적으로 동작하며, 다양한 실생활 문제에 적용할 수 있다.