다익스트라(Dijkstra) 알고리즘
다익스트라 알고리즘은 하나의 정점(출발 노드)에서 다른 모든 정점까지의 최단 경로를 찾는 알고리즘입니다.
이 알고리즘이 올바르게 동작하기 위한 두 가지 전제 조건이 있습니다.
-
시작점이 정해져 있어야 합니다 (Single-Source).
-
그래프의 모든 간선(Edge)의 가중치는 양수여야 합니다
💡 핵심 원리: 더 가까운 곳부터 탐색한다
다익스트라 알고리즘은 '탐욕법(Greedy Algorithm)'에 기반합니다. 그 핵심 아이디어는 아주 간단합니다.
"지금까지 발견된 경로 중, 출발점에서부터의 총거리가 가장 짧은 노드를 먼저 방문하여 경로를 확정한다."이 과정을 모든 노드를 방문할 때까지 반복하면, 결국 출발점에서 모든 노드까지의 최단 경로를 알게 됩니다.
알고리즘의 주요 단계
-
그래프 준비: 입력받은 간선 정보를 인접 리스트로 구현합니다.
-
초기화: 출발 노드의 거리는 0, 나머지 모든 노드의 거리는 무한대(∞)로 설정한 최단 거리 배열을 만듭니다.
-
우선순위 큐: (거리, 노드) 쌍을 관리하는 우선순위 큐를 만들고, 시작점 정보 (0, 시작노드)를 넣습니다.
-
반복: 큐가 빌 때까지 다음을 반복합니다.
-
가장 가까운 노드 선택: 큐에서 현재 가장 거리가 짧은 노드를 꺼냅니다. 이 노드의 최단 거리는 이제 '확정'됩니다.
-
경로 갱신: 해당 노드를 거쳐 갈 수 있는 이웃 노드들의 거리를 계산합니다. 만약 기존에 알려진 거리보다 더 짧은 경로를 발견하면, 최단 거리 배열을 갱신하고 우선순위 큐에 새로운 정보를 추가합니다.
-
🤔 우선순위 큐, 왜 꼭 써야 할까?
이 질문이 다익스트라를 이해하는 가장 중요한 관문입니다. "어차피 모든 노드를 다 방문할 텐데, 왜 굳이 우선순위 큐를 써야 할까?"
결론부터 말하면, 우선순위 큐는 알고리즘의 효율성뿐만 아니라 정확성을 보장하는 핵심 장치입니다.
일반 큐는 '먼저 들어온 순서(FIFO)'대로 처리하기 때문에, 우연히 먼저 발견된 경로가 비용이 비싸더라도 목적지에 먼저 도착하면 그 경로를 최단 경로라고 성급하게 확정해버릴 수 있습니다.
반면 우선순위 큐는 항상 '비용이 가장 낮은 순서'대로 처리합니다. 이는 "현재까지 알려진 가장 저렴한 경로를 먼저 확정"하는 다익스트라의 황금률을 지켜주어, 알고리즘이 올바른 답을 찾도록 보장합니다.
💻 [백준] 1753번 - 최단 경로 구하기
파이썬에서는 heapq 모듈을 사용하여 우선순위 큐를 효율적으로 구현할 수 있습니다.
import sys
import heapq
# 입력 처리를 빠르게 하기 위함
input = sys.stdin.readline
# 노드 개수(V), 간선 개수(E)
V, E = map(int, input().split())
# 시작 노드 번호
K = int(input())
# 그래프를 표현할 인접 리스트
graph = [[] for _ in range(V + 1)]
# 최단 거리를 저장할 배열, 무한대로 초기화
dist = [sys.maxsize] * (V + 1)
# 간선 정보 입력받기
for _ in range(E):
u, v, w = map(int, input().split())
# u번 노드에서 v번 노드로 가는 가중치가 w
graph[u].append((v, w))
def dijkstra(start):
# 우선순위 큐(최소 힙) 생성
que = []
# 시작 노드로 가기 위한 최단 경로는 0으로 설정하여 큐에 삽입
heapq.heappush(que, (0, start))
dist[start] = 0
# 큐가 비어있지 않은 동안 반복
while que:
# 가장 최단 거리가 짧은 노드에 대한 정보 꺼내기
current_dist, current_node = heapq.heappop(que)
# 이미 처리된 적 있는 노드라면 무시
# (큐에 남아있는 옛날 정보보다 현재 기록된 최단거리가 더 짧을 경우)
if dist[current_node] < current_dist:
continue
# 현재 노드와 연결된 다른 인접한 노드들을 확인
for neighbor_node, weight in graph[current_node]:
new_dist = current_dist + weight
# 현재 노드를 거쳐서, 다른 노드로 이동하는 거리가 더 짧은 경우
if new_dist < dist[neighbor_node]:
dist[neighbor_node] = new_dist
heapq.heappush(que, (new_dist, neighbor_node))
# 다익스트라 알고리즘 수행
dijkstra(K)
# 모든 노드로 가기 위한 최단 거리를 출력
for i in range(1, V + 1):
if dist[i] == sys.maxsize:
print("INF")
else:
print(dist[i])📊 시간 복잡도 분석
다익스트라 알고리즘의 시간 복잡도는 어떤 자료구조를 사용해 '최단 거리 노드'를 찾는지에 따라 달라집니다.
-
배열/리스트 사용 시: 매번 모든 노드를 순회하며 최소 거리를 찾아야 하므로 가 걸리고, 이 과정을 V번 반복하여 총 의 시간 복잡도를 가집니다.
-
우선순위 큐(힙) 사용 시: 큐에서 원소를 빼거나 넣는 데 가 걸립니다. 모든 간선을 한 번씩 확인(E)하므로, 총 시간 복잡도는 가 됩니다. 일반적으로 이 방식이 훨씬 효율적입니다.
## 맺음말
다익스트라 알고리즘은 개념적으로 조금 헷갈릴 수 있지만, '가장 가까운 곳부터 확정한다'는 탐욕적인 아이디어와 '우선순위 큐'의 역할만 정확히 이해하면 누구나 정복할 수 있습니다. 이 글이 다익스트라 알고리즘을 공부하는 데 도움이 되었기를 바랍니다.
