[알고리즘] 벨만-포드 알고리즘 파이썬으로 구현하기 | 음수 사이클 조회하는 방법

벨만-포드 알고리즘(Bellman-Ford algorithm)은 특정 출발 노드에서 다른 모든 노드까지의 최단 경로를 구하는 알고리즘입니다. 특징 중 하나는 엣지의 가중치가 음수여도 활용이 가능하다는 점이며, 이러한 음수 사이클의 존재 여부를 판별하는 것이 벨만-포드 알고리즘의 중요한 것 중 하나 입니다. 벨만-포드 알고리즘의 구체적인 작동 원리는 아래와 같이 구현할 수 있습니다.

1단계 : 초기화

벨만-포드 알고리즘은 엣지를 중심으로 동작하기 때문에 엣지 리스트를 구현합니다. 이전 다른 그래프 경우와 유사하게, 거리 리스트에 대해서는 출발 노드는 0, 나머지 노드는 무한대로 초기화도 수행합니다.

 

graph = [] # 에지 리스트
for _ in range(num_edge):
    u, v, w = map(int, input().split())
    graph.append((u, v, w))

D = [float('inf')] * n  # 노드의 개수
D[start] = 0

2단계 : 거리 리스트 업데이트

모든 에지를 확인해 총 (n-1)번 거리 리스트를 업데이트합니다. (D[e] = D[s] + w) 업데이트를 수행하기 위한 AND 조건은 다음과 같습니다. 

• D[s] != inf
• D[e] > D[s] + w

for _ in range(n-1):
    for s, e, w in graph:
        if D[s] != float('inf') and D[e] > D[s] + w:
            D[e] = D[s] + w

3단계 : 음수 사이클 탐지 

에지 리스트에 있는 모든 에지에 대해서 위에서 언급한 조건을 만족하는 경우에는 음수 사이클이 존재하는 것을 알 수 있습니다. 

 

    for s, e, w in graph:
        if D[s] != float('inf') and D[e] > D[s] + w:
            return None
    return D

최종 코드

위에서 설명한 단계에 따른 최종 코드는 아래와 같이 구현할 수 있습니다.

 

graph = []
for _ in range(num_edge):
    u, v, w = map(int, input().split())
    graph.append((u, v, w))

def bellman_ford(start, graph):
    D = [float('inf')] * n     # 노드의 개수
    D[start] = 0

    for _ in range(n-1):
        for s, e, w in graph:
            if D[s] != float('inf') and D[e] > D[s] + w:
                D[e] = D[s] + w

    for s, e, w in graph:
        if D[s] != float('inf') and D[e] > D[s] + w:
            return None
    return D

참고자료

[1] 위키피디아 : 벨먼 - 포드 알고리즘

벨먼-포드 알고리즘 - 위키백과, 우리 모두의 백과사전

[2] Do it! 알고리즘 코딩 테스트 : 파이썬 편