둘 다 가중 그래프에서 출발점으로부터의 최단 경로를 찾습니다. Dijkstra는 더 빠르지만 음이 아닌 가중치가 필요하고, Bellman-Ford는 더 느리지만 음수 간선을 처리하고 음수 사이클을 탐지합니다.
Dijkstra (greedy + min-heap)
방문하지 않은 가장 가까운 노드를 반복적으로 확장하고 그 이웃을 relax(완화)합니다.
python
import heapq
def dijkstra(graph, src):
dist = {n: float('inf') for n in graph}
dist[src] = 0
pq = [(0, src)] # (거리, 노드)
while pq:
d, u = heapq.heappop(pq) # 가장 가까운 것부터
if d > dist[u]:
continue
for v, w in graph[u]:
if d + w < dist[v]: # 간선 relax
dist[v] = d + w
heapq.heappush(pq, (dist[v], v))
return dist
모든 간선을 V-1번 relax합니다. 추가 relaxation이 발생하면 음수 사이클을 의미합니다.
| Dijkstra | Bellman-Ford | |
|---|---|---|
| 가중치 | 음이 아님 | 임의(음수 포함) |
| 시간 | O((V+E) log V) | O(V·E) |
| 음수 사이클 | 해당 없음 | 탐지함 |
음이 아닌 가중치(지도, 네트워크)에는 기본적으로 Dijkstra를 사용하세요. 음수 간선이 존재할 때(예: 차익 거래)는 Bellman-Ford를 사용하세요. Dijkstra는 음수 가중치에서 조용히 깨집니다 — 전형적인 함정입니다.
최단 경로 알고리즘은 라우팅, 내비게이션, 네트워크 프로토콜, 의존성 비용 분석을 뒷받침합니다.
Dijkstra의 음이 아닌 가중치 제약을 아는 것은 현장에서 틀린 답을 방지합니다.
relaxation 아이디어는 greedy와 DP 사고를 연결하여 풍부한 시니어 수준 주제로 만듭니다.
주니어부터 시니어까지 상세한 답변이 포함된 IT 면접 질문 라이브러리.
후원하기