| 다익스트라 | 벨만포드 | |
| 사용 | 양의 간선만 있을 때 최단 거리 | 음의 간선이 있을 때 최단 거리 음수 사이클 탐지에도 사용 |
| 시간복잡도 | O(M log N) - M: 간선, N: 노드 | O(NM) |
| 음수 가중치가 없다면, 다익스트라가 압도적으로 빠르기 때문에 다익스트라 사용 | 음수 가중치나 음수 사이클이 있을 때만 사용 권장 |
다익스트라
최단 거리 테이블을 조금씩 갱신하며 완성해내가는 알고리즘
예시
(2)
1 ----- 2
| / |
(5) (1) (3)
| / |
3 ----- 4
(2)- 노드: 1~4
- 간선: (1-2, 2), (1-3, 5), (2-3, 1), (2-4, 3), (3-4, 2)
🟢 초기 상태
- distance: [inf, 0, inf, inf, inf]
- pq: [(0, 1)]
▶ 1단계: 1번 노드 방문
- 인접한 간선들:
- (1→2, 2) → 거리 2 → 업데이트!
- (1→3, 5) → 거리 5 → 업데이트!
- distance: [inf, 0, 2, 5, inf]
- pq: [(2, 2), (5, 3)]
▶ 2단계: 2번 노드 방문(거리 2)
- 인접한 간선들:
- (2→3, 1) → 현재 거리 = 2+1 = 3 → 기존 5보다 작다! 업데이트!
- (2→4, 3) → 2+3 = 5 → 업데이트!
- distance: [inf, 0, 2, 3, 5]
- pq: [(3, 3), (5, 3), (5, 4)]
▶ 3단계: 3번 노드 방문(거리 3)
- 인접한 간선들:
- (3→4, 2) → 3+2 = 5 → 기존 5와 같음 → 업데이트 X
- distance: [inf, 0, 2, 3, 5]
- pq: [(5, 3), (5, 4)]
▶ 4단계: 3번 노드 재방문 -> 이미 짧은 거리로 방문했으므로 무시
- pq: [(5, 4)]
▶ 5단계: 4번 노드 방문(거리 5) -> 인접 노드 없음 -> 끝코드
import heapq
def dijkstra(start, graph, n):
distance = [float('inf')] * (n + 1)
distance[start] = 0
pq = [(0, start)]
while pq:
dist, now = heapq.heappop(pq)
if distance[now] < dist:
continue
for nxt, cost in graph[now]:
new_cost = dist + cost
if new_cost < distnace[nxt]:
distance[nxt] = new_cost
heapq.heappush(pq, (new_cost, nxt))
return distance벨만 포드
음의 간선을 포함한 그래프에서 최단거리 계산하는 알고리즘
예시
(2)
1 ----- 2
| / |
(5) (1) (3)
| / |
3 ----- 4
(2)
- 노드: 1~4
- 간선: (1-2, 2), (1-3, 5), (2-3, 1), (2-4, 3), (3-4, 2)
🟢 초기 상태
- distance: [0, inf, inf, inf, inf]
▶ 1회차(간선 1개로만 연결되어있는 노드 처리)
노드 1까지 거리: 0
노드 2까지 거리: 2
노드 3까지 거리: 5
노드 4까지 거리: inf
▶ 2회차(간선 2개로 연결되어있는 노드 처리)
노드 1까지 거리: 0
노드 2까지 거리: 2
노드 3까지 거리: 3 (distance[2] + 1)
노드 4까지 거리: 5 (distance[2] + 3)
▶ 3회차(간선 3개로 연결되어있는 노드 처리)
노드 1까지 거리: 0
노드 2까지 거리: 2
노드 3까지 거리: 3
노드 4까지 거리: 5 코드
def bellman_ford(n, edges, start):
dist = [float('inf')] * (n + 1)
dist[start] = 0
for i in range(n - 1):
for u, v, cost in edges:
if dist[u] + cost < dist[v]:
dist[v] = dist[u] + cost
# 음수 사이클 확인
for u, v, cost in edges:
if dist[u] + cost < dist[v]:
return None # 음수 사이클 있음
return dist