벨만-포드 알고리즘 bellman-ford

벨만-포드 알고리즘

• 가중치 그래프에서 단일 출발점에서 모든 다른 노드까지의 최단 경로를 구하는 알고리즘
• 다익스트라와 다르게, 음수 가중치 엣지도 다룰수있다.
• 주요 특징
  • 단일 출발점에서의 모든 노드의 최단 경로를 찾는다.
  • 음수 가중치를 고려할 수 있다.
  • 가중치가 음수인 사이클이 존재하는지 탐지 할 수 있다.
    • 만약 음수 가중치 사이클 존재시, 최단 경로가 무한대로 감소할 수 있으니...
• 알고리즘 단계
  • 1. 초기화
    • 출발 노드의 거리를 0으로 설정. 나머지 노드는 무한대로 초기화.
  • 2. 릴렉스( 현재 알고 있는 최단 경로를 더 짧게 만들수 있는지 확인하고 업데이트 하는 과정 )
    • 모든 엣지에 대해서 V-1번(노드의 갯수 V에서 1을 뺀 만큼) 만큼 릴렉스를 반복한다.
  • 3. 음수 가중치 사이클 탐지
• 시간 복잡도: V*E이다. 즉, 노드의 갯수와 엣지의 갯수에 비례한다.

 

INF = float('inf')

def bellman_ford( graph , V , start ):
    distance = [INV] * V # 거리 배열의 초기화. 모든 노드의 거리를 무한대로 설정
    distance[ start ] = 0 # 출발 노드의 거리는 0이다.
    for u , v , w in graph:
        if distance[ u ] != INF and distance[ u ] + w < distance[ v ]:
            distance[ v ] = distance[ u ] + w

    for u , v , w in graph:
        if distance[ u ] != INF and distance[ u ] + w <distance[ v ]:
            print(" 음수 가중치 사이클 존재")
            return None

    return distance

ex = [
    (0, 1, 5),   # 노드 0에서 노드 1로 가는 경로의 가중치가 5
    (0, 2, 4),   # 노드 0에서 노드 2로 가는 경로의 가중치가 4
    (1, 3, 3),   # 노드 1에서 노드 3으로 가는 경로의 가중치가 3
    (2, 1, 6),   # 노드 2에서 노드 1로 가는 경로의 가중치가 6
    (3, 2, -2),  # 노드 3에서 노드 2로 가는 경로의 가중치가 -2 (음수)
]

V = 4
distances = bellman_ford( ex , V , 0 )

if distances:
    print("각 노드별 최단 거리:")
    for i in range ( V ):
        print(f"노드 0에서 노드 {i}까지의 거리: {distances[i]}")