벨만-포드 알고리즘(Bellman-Ford Algorithm)

벨만-포드 알고리즘

"가중치가 있는 그래프에서 최단 경로를 찾는 알고리즘으로, 음의 가중치(음수 간선)도 처리 가능하다!"

• 다익스트라와 달리 음수 가중치가 있는 그래프에서도 사용 가능
• 모든 간선을 최대 V-1번 반복하여 최단 경로를 업데이트하는 방식
• 음수 사이클(무한히 거리가 줄어드는 경우)도 감지 가능

---

벨만-포드 알고리즘 동작 원리

1. 모든 노드까지의 최단 거리를 무한(∞)으로 초기화, 단 시작 노드는 0으로 설정
2. 그래프의 모든 간선을 V-1번 반복하며 갱신 (V는 노드 개수)
3. V번째 반복에서 값이 갱신되면 음수 사이클이 존재함!

출처: https://mantaray.tistory.com/13

# Pseudo Code
FUNCTION BellmanFord(graph, start):
    거리 = {모든 노드를 ∞(무한대)로 초기화}
    거리[start] = 0  # 시작 노드는 0

    FOR i FROM 1 TO V-1 DO:  # (V-1)번 반복
        FOR (u, v, weight) IN 모든 간선:
            IF 거리[u] + weight < 거리[v]:
                거리[v] = 거리[u] + weight

    # 음수 사이클 확인
    FOR (u, v, weight) IN 모든 간선:
        IF 거리[u] + weight < 거리[v]:
            RETURN "음수 사이클 존재!"

    RETURN 거리


# Full Code
def bellman_ford(graph, start, V):
    distances = {node: float('inf') for node in graph}  # 거리 초기화
    distances[start] = 0  # 시작 노드는 거리 0

    # V-1번 반복 (최대 V-1개의 간선 사용 가능)
    for _ in range(V - 1):
        for u in graph:
            for v, weight in graph[u]:  # 모든 간선 확인
                if distances[u] + weight < distances[v]:
                    distances[v] = distances[u] + weight  # 거리 갱신

    # 음수 사이클 확인
    for u in graph:
        for v, weight in graph[u]:
            if distances[u] + weight < distances[v]:
                return "음수 사이클 존재!"  # 무한히 감소하는 경로 발견

    return distances  # 최단 거리 반환

# 그래프 정의 (인접 리스트)
graph = {
    1: [(2, 4), (3, 3)],
    2: [(4, 2)],
    3: [(2, -1), (4, 5)],
    4: []
}

start_node = 1
V = len(graph)
shortest_paths = bellman_ford(graph, start_node, V)
print(shortest_paths)

---

벨만-포드 알고리즘의 시간복잡도

경우	시간복잡도
최선 (간선이 적고 빠르게 갱신 완료)	O(E)
평균	O(VE)
최악 (V-1번 반복하며 모든 간선 체크)	O(VE)

 

✅ 간선이 많을수록 느림 → O(VE) (V=노드, E=간선)
✅ 희소 그래프(간선이 적은 그래프)에서는 다익스트라가 더 빠름

---

벨만-포드 알고리즘의 장단점

장점

• 음수 가중치가 있는 그래프에서도 동작 가능
• 음수 사이클(무한히 거리가 줄어드는 경로) 탐지 가능
• 모든 노드까지의 최단 경로를 한 번에 계산 가능

단점

• 다익스트라(O((V+E) log V))보다 느림 (O(VE))
• 간선 개수가 많으면 성능이 급격히 저하됨 (V가 클 때 비효율적)

결론

벨만-포드 알고리즘은 음수 가중치가 있는 경우에도 최단 경로를 구할 수 있으며, 음수 사이클을 감지할 수 있다. 하지만 성능이 O(VE)로 느리므로, 일반적으로 다익스트라 알고리즘을 더 많이 사용한다.