[Daily morning study] 다익스트라와 벨만-포드 최단 경로 알고리즘
#daily morning study
최단 경로 문제
그래프에서 두 정점 사이의 가중치 합이 최소인 경로를 찾는 문제다. 대표적인 알고리즘으로 다익스트라(Dijkstra)와 벨만-포드(Bellman-Ford)가 있으며, 각각 적용 가능한 조건과 시간 복잡도가 다르다.
다익스트라 알고리즘
핵심 아이디어
탐욕적(Greedy) 접근을 사용한다. 아직 방문하지 않은 정점 중 현재까지의 거리가 가장 짧은 정점을 선택해 인접한 정점들의 거리를 갱신한다. 음수 가중치가 없을 때만 올바르게 동작한다.
동작 원리
- 시작 정점의 거리를 0, 나머지를 무한대(∞)로 초기화
- 미방문 정점 중 거리 최솟값을 가진 정점
u선택 u의 모든 인접 정점v에 대해dist[u] + weight(u, v) < dist[v]이면 거리 갱신 (relax)u를 방문 완료로 표시- 모든 정점을 방문할 때까지 2~4 반복
한 번 방문 완료된 정점의 거리는 최종값이다. 음수 가중치가 있으면 이 보장이 깨진다.
우선순위 큐를 이용한 구현
단순 배열로 최솟값을 선형 탐색하면 O(V²)이지만, 최소 힙(Min-Heap)을 사용하면 O((V + E) log V)로 개선된다.
import heapq
def dijkstra(graph, start, n):
# graph[u] = [(v, weight), ...]
dist = [float('inf')] * n
dist[start] = 0
heap = [(0, start)] # (distance, vertex)
while heap:
d, u = heapq.heappop(heap)
# 이미 더 짧은 경로로 처리됐으면 스킵
if d > dist[u]:
continue
for v, w in graph[u]:
if dist[u] + w < dist[v]:
dist[v] = dist[u] + w
heapq.heappush(heap, (dist[v], v))
return dist
복잡도
| 구현 방식 | 시간 복잡도 |
|---|---|
| 단순 배열 (선형 탐색) | O(V²) |
| 이진 힙 (heapq) | O((V + E) log V) |
| 피보나치 힙 | O(V log V + E) |
밀집 그래프(E ≈ V²)에서는 배열 방식이, 희소 그래프에서는 힙 방식이 유리하다.
벨만-포드 알고리즘
핵심 아이디어
동적 계획법(DP) 접근을 사용한다. 모든 간선을 V-1번 반복해서 완화(relax)하면, 최대 V-1개의 간선을 거치는 최단 경로를 모두 구할 수 있다. 음수 가중치 간선을 허용하며, 음수 사이클 존재 여부도 감지할 수 있다.
동작 원리
- 시작 정점의 거리를 0, 나머지를 ∞로 초기화
- 모든 간선 (u, v, w)에 대해
dist[u] + w < dist[v]이면 dist[v] 갱신 - 2를 V-1번 반복 (정점 수 - 1)
- V번째 반복에서도 갱신이 발생하면 음수 사이클이 존재
V-1번 반복 이유: V개 정점의 최단 경로에서 간선은 최대 V-1개를 사용한다. 각 반복마다 적어도 하나의 간선을 더 고려하므로 V-1번이면 충분하다.
구현
def bellman_ford(edges, start, n):
# edges = [(u, v, weight), ...]
dist = [float('inf')] * n
dist[start] = 0
for i in range(n - 1):
updated = False
for u, v, w in edges:
if dist[u] != float('inf') and dist[u] + w < dist[v]:
dist[v] = dist[u] + w
updated = True
# 더 이상 갱신이 없으면 조기 종료
if not updated:
break
# 음수 사이클 감지
for u, v, w in edges:
if dist[u] != float('inf') and dist[u] + w < dist[v]:
return None # 음수 사이클 존재
return dist
복잡도
- 시간: O(V × E)
- 공간: O(V)
두 알고리즘 비교
| 항목 | 다익스트라 | 벨만-포드 |
|---|---|---|
| 음수 가중치 | 불가 | 가능 |
| 음수 사이클 감지 | 불가 | 가능 |
| 시간 복잡도 | O((V+E) log V) | O(V·E) |
| 단일 출발 최단 경로 | 가능 | 가능 |
| 접근 방식 | 그리디 | 동적 계획법 |
음수 가중치가 있으면 다익스트라가 왜 틀리는가
예시 그래프:
- A → B: 2
- A → C: 3
- C → B: -2
다익스트라는 A에서 B로 거리 2를 확정 후 C를 처리한다. 그러나 A → C → B = 3 + (-2) = 1이 더 짧다. B가 이미 방문 완료로 표시됐기 때문에 더 짧은 경로를 무시한다. 벨만-포드는 모든 간선을 반복적으로 완화하므로 이 경우도 올바른 결과를 낸다.
활용 사례
다익스트라
- 네비게이션 최단 경로 (도로 가중치는 항상 양수)
- 네트워크 라우팅 프로토콜 (OSPF)
- 게임 맵의 경로 탐색
벨만-포드
- 금융 차익 거래 감지 (음수 사이클 = 차익 기회)
- BGP 라우팅에서 거리 벡터 계산
- 네트워크 비용 모델에 음수 가중치가 포함될 때
SSSP vs APSP
- SSSP (Single-Source Shortest Path): 단일 출발지 → 모든 정점. 다익스트라, 벨만-포드가 여기에 해당.
- APSP (All-Pairs Shortest Path): 모든 쌍의 최단 거리. 플로이드-워셜(O(V³))이 대표적.
SSSP를 V번 실행해도 APSP를 구할 수 있지만, 플로이드-워셜이 구현이 단순하고 밀집 그래프에서 실용적이다.
경로 복원
최단 거리뿐 아니라 경로 자체가 필요할 때 parent 배열을 함께 관리한다.
# 다익스트라에 경로 복원 추가
parent = [-1] * n
# relax 시점에 parent 갱신
if dist[u] + w < dist[v]:
dist[v] = dist[u] + w
parent[v] = u
heapq.heappush(heap, (dist[v], v))
# 경로 추적
def get_path(parent, target):
path = []
cur = target
while cur != -1:
path.append(cur)
cur = parent[cur]
return path[::-1]