최단경로 (다익스트라, 벨만포드, BFS)
그래프에서 한 점에서 다른 점으로 가는 가장 빠른 길을 찾는 문제가 최단 경로(Shortest Path)이다. 네비게이션의 길찾기, 라우터의 패킷 전달, 비행기 노선 설계, SNS의 친구 추천, 게임 캐릭터의 이동 AI까지 — 그래프 위에서 동작하는 거의 모든 응용의 토대가 최단 경로 알고리즘이다. 가중치의 유무·음수 가중치 허용 여부·시작점이 하나인지 모두인지에 따라 적합한 알고리즘이 갈리며, 그 선택의 정확성이 시스템의 응답 시간을 직접 결정한다. 본 글은 BFS·다익스트라·벨만-포드·플로이드-워셜 네 가지 핵심 최단 경로 알고리즘의 차이와 사용 조건을 세심하게 정리한다(출처: CLRS — Introduction to Algorithms, 22~25장). 제가 학교 알고리즘 과제에서 노드 1만짜리 그래프에 다익스트라를 우선순위 큐 없이 짰다가 30초 걸리던 코드를 힙으로 갈아 끼우자 0.3초로 떨어지는 모습을 본 후로는 "최단 경로의 90%는 자료구조 선택"이라는 인상을 손끝으로 받아들였다.
최단 경로 문제의 분류와 알고리즘 선택
최단 경로 문제는 두 가지 축으로 분류된다. 시작점이 하나인가 모두인가, 그리고 가중치가 어떤 종류인가이다. 시험에서 자주 출제되는 분류이며, 이 분류만 정확히 잡으면 어느 알고리즘을 쓸지 거의 자동으로 결정된다.
| 분류 | 알고리즘 | 시간복잡도 | 음수 가중치 |
|---|---|---|---|
| 비가중 + 한 시작점 | BFS | O(V + E) | — |
| 비음 가중치 + 한 시작점 | 다익스트라 (힙) | O((V+E) log V) | 불가 |
| 음 가중치 허용 + 한 시작점 | 벨만-포드 | O(V·E) | 가능 + 음수 사이클 검출 |
| 모든 쌍의 최단 경로 | 플로이드-워셜 | O(V³) | 가능 |
여기서 음수 사이클(negative cycle)이란 사이클 위의 간선 가중치 합이 음수인 사이클을 가리키며, 이런 사이클이 있으면 무한히 돌며 거리를 줄일 수 있어 최단 경로 자체가 정의되지 않는다. 다익스트라가 음 가중치를 처리하지 못하는 결정적 이유가 바로 이 사이클 가능성 때문이며, 음 가중치가 가능한 환경(예: 환율 차익 거래·일부 게임 AI)에서는 벨만-포드를 써야 한다.
# 1) BFS — 비가중 그래프 최단 경로
from collections import deque
def bfs_shortest(graph, start):
dist = {start: 0}
q = deque([start])
while q:
u = q.popleft()
for v in graph[u]:
if v not in dist:
dist[v] = dist[u] + 1
q.append(v)
return distBFS가 비가중 그래프에서 최단 경로를 보장하는 이유는 너비 우선으로 같은 깊이를 모두 본 뒤 다음 깊이로 넘어가기 때문이다. 따라서 한 노드를 처음 방문하는 시점의 깊이가 곧 그 노드까지의 최단 거리가 된다.
다익스트라 — 비음 가중치의 표준
다익스트라 알고리즘(Dijkstra's Algorithm)은 1956년 에츠허르 다익스트라가 제안한 비음 가중치 그래프의 표준 최단 경로 알고리즘이다. 핵심 아이디어는 현재까지 알려진 가장 가까운 노드를 매번 확정해 가는 그리디 전략이다. 한 번 확정된 노드는 그 거리가 곧 최단 거리임이 보장된다는 성질이 이 알고리즘의 정확성을 뒷받침한다.
import heapq
def dijkstra(graph, start):
# graph: {u: [(v, weight), ...], ...}
dist = {u: float('inf') for u in graph}
dist[start] = 0
pq = [(0, start)] # (현재 거리, 노드)
while pq:
d, u = heapq.heappop(pq)
if d > dist[u]: continue # 이미 더 짧은 거리 발견
for v, w in graph[u]:
nd = d + w
if nd < dist[v]:
dist[v] = nd
heapq.heappush(pq, (nd, v))
return dist다익스트라의 시간복잡도는 자료구조 선택이 결정한다. 단순 배열로 구현하면 매 단계 미방문 노드 중 최솟값 검색에 O(V)가 들어 전체 O(V²)이다. 이진 힙(최소 힙)으로 우선순위 큐를 구현하면 O((V+E) log V)로 떨어지며, 이게 실무 표준이다. 피보나치 힙을 쓰면 O(E + V log V)로 더 빨라지지만 구현 복잡도가 커서 거의 사용되지 않는다.
다익스트라가 음 가중치에서 실패하는 이유는 한 번 확정한 노드의 거리가 뒤에 음 간선 때문에 더 작아질 수 있는데, 다익스트라는 확정 후 재방문하지 않기 때문이다. 솔직히 제 경험상 학교 시험에서 이 함정이 가장 자주 출제되었고, "다익스트라 = 비음 가중치 + 우선순위 큐" 한 줄을 외운 사람만 안정적으로 정답을 맞췄다.
벨만-포드와 플로이드-워셜 — 음 가중치와 모든 쌍
벨만-포드 알고리즘(Bellman-Ford)은 음 가중치가 가능한 그래프에서 동작하는 단일 시작점 최단 경로 알고리즘이다(출처: 위키백과 — Bellman-Ford algorithm). V-1번 모든 간선을 완화(relaxation)하는 단순한 알고리즘이며, 시간복잡도는 O(V·E)로 다익스트라보다 느리지만 음 가중치를 다룰 수 있다는 결정적 강점이 있다. 또한 V번째 반복에서 거리가 더 줄어들면 음수 사이클이 존재한다는 사실을 즉시 검출할 수 있다.
여기서 완화(relaxation)란 간선 (u, v)을 따라 가면 더 짧은 경로가 만들어지는지 확인해 dist[v]를 갱신하는 단일 연산을 가리키며, if dist[u] + w(u,v) < dist[v]: dist[v] = dist[u] + w(u,v) 한 줄이 정확히 완화이다. 다익스트라·벨만-포드 모두 본질적으로는 완화의 반복 적용이며, 차이는 어떤 순서로 완화하느냐일 뿐이다.
def bellman_ford(edges, V, start):
# edges: [(u, v, w), ...]
dist = [float('inf')] * V
dist[start] = 0
for _ in range(V - 1):
for u, v, w in edges:
if dist[u] + w < dist[v]:
dist[v] = dist[u] + w
# 음수 사이클 검출
for u, v, w in edges:
if dist[u] + w < dist[v]:
return None # 음수 사이클 존재
return dist플로이드-워셜 알고리즘(Floyd-Warshall)은 모든 노드 쌍 사이의 최단 경로를 한 번에 구하는 DP 기반 알고리즘이다. 시간복잡도가 O(V³)이라 큰 그래프에는 적합하지 않지만, V가 수백 이하인 작은 그래프에서는 압도적으로 단순한 구현과 모든 쌍의 답을 한 번에 얻는 강점이 결정적이다. 핵심 점화식은 dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])로, 중간 경유지 k를 0번부터 V-1번까지 차례로 허용해 가면서 거리를 갱신한다.
def floyd_warshall(graph):
V = len(graph)
dist = [row[:] for row in graph] # 인접 행렬 복사
for k in range(V):
for i in range(V):
for j in range(V):
if dist[i][k] + dist[k][j] < dist[i][j]:
dist[i][j] = dist[i][k] + dist[k][j]
return dist세 줄짜리 핵심 반복이 모든 쌍의 최단 경로를 만들어 낸다는 점이 가장 인상적이다. 솔직히 이건 예상 밖이었는데, 학교에서 처음 플로이드-워셜이 5줄짜리 알고리즘이라는 사실을 알게 된 후로는 "단순함은 알고리즘의 무기"라는 점을 받아들였다.
알고리즘 선택 가이드와 실전 응용
상황별로 어떤 알고리즘을 선택해야 하는지 한 표로 정리하면 다음과 같다.
| 상황 | 알고리즘 | 이유 |
|---|---|---|
| 미로 최단 거리·소셜 거리 | BFS | 비가중 + 단일 시작점 |
| 네비게이션·게임 길찾기 | 다익스트라 (힙) | 비음 가중치 + 빠름 |
| 환율 차익·임의 가중치 | 벨만-포드 | 음 가중치 허용 + 사이클 검출 |
| 작은 그래프 + 모든 쌍 | 플로이드-워셜 | 5줄 구현 + 모든 답 |
| 휴리스틱 가능 (게임 AI) | A* | 다익스트라 + 휴리스틱 |
여기서 A*(에이스타) 알고리즘이란 다익스트라에 "목표까지의 추정 거리(heuristic)"를 더해 우선순위를 매기는 변형으로, 휴리스틱이 정확할수록 다익스트라보다 훨씬 적은 노드만 탐색해도 같은 답을 보장한다. 게임 NPC의 길찾기, 자율주행 경로 계획, 퍼즐 풀이의 표준이다.
마지막으로 시험 답안에서 자주 쓰이는 정형 표현을 정리하면, "최단 경로 알고리즘은 가중치와 시작점 수에 따라 BFS(비가중·단일), 다익스트라(비음·단일), 벨만-포드(음 가능·단일·O(VE)·음수 사이클 검출), 플로이드-워셜(모든 쌍·O(V³))로 분류되며, 다익스트라는 우선순위 큐(이진 힙)로 구현해 O((V+E) log V)에 동작한다"는 두 문장이 표준 답안 표현으로 통한다. 다음 글에서는 최소 신장 트리(MST)·위상 정렬 같은 그래프 알고리즘의 다른 갈래를 이어 다룬다.
메타 디스크립션: 그래프의 최단 경로 4대 알고리즘(BFS·다익스트라·벨만-포드·플로이드-워셜)의 차이와 시간복잡도, 음수 가중치·음수 사이클 처리, 그리고 자료구조 선택에 따른 다익스트라 성능 차이를 알고리즘 입문자 관점에서 세심하게 정리합니다.