[python] 벨만-포드 알고리즘

최단 경로 알고리즘

• 그래프에서 노드 간의 최소 비용 경로를 찾는 알고리즘.
• 주로 길 찾기 문제에 적용되며, 그래프의 각 지점을 노드로, 지점 간 연결된 도로를 간선으로 표현.

대표 알고리즘

• 다익스트라
• 벨만-포드
• 플로이드와샬

벨만-포드

• 음수 간선이 있을때 쓸 수 있는 최단 경로 알고리즘
• 특징
  • 단일 출발점 최단 경로 알고리즘
  • 음수 가중치 간선을 포함한 그래프에서 사용 가능
  • 음수 사이클 감지 기능
• 동작 원리
  • 시작 노드의 거리를 0으로 초기화
  • 모든 다른 노드의 거리를 무한대로 설정
  • (노드 수 - 1)번 반복하며 모든 간선 완화
  • 마지막으로 음수 사이클 존재 여부 확인
• 성능 및 장단점
  • 시간 복잡도 O(VE)로 다익스트라보다 느리다는 단점
  • 하지만 음수 가중치가 있어도 사용 가능

코드

def bellman_ford(graph, start):
    # 거리 초기화
    distance = {node: float('inf') for node in graph}
    distance[start] = 0

    # (노드 수 - 1)번 반복
    for _ in range(len(graph) - 1):
        for node in graph:
            for neighbor, weight in graph[node].items():
                # 간선 완화
                if distance[node] + weight < distance[neighbor]:
                    distance[neighbor] = distance[node] + weight

    # 음수 사이클 확인
    for node in graph:
        for neighbor, weight in graph[node].items():
            if distance[node] + weight < distance[neighbor]:
                return "음수 사이클 존재"

    return distance

# 예시 그래프
graph = {
    'A': {'B': 4, 'C': 2},
    'B': {'C': 3, 'D': 2, 'E': 3},
    'C': {'B': 1, 'D': 4, 'E': 5},
    'D': {},
    'E': {'D': -5}
}

# 시작 노드
start_node = 'A'

# 벨만-포드 알고리즘 실행
result = bellman_ford(graph, start_node)
print(result)