최단 경로 벨만 포드

벨만 포드

다익스트라 관련 알고리즘 문제를 풀다가 알게된 알고리즘이다. 다익스트라와 비슷하지만 차이점은 음수 간선이 포함되어 있을 때도 최단 경로를 구할 수 있다는 점이다.

 

벨만 포드에서 주목해야 할 부분은 음수 간선을 포함하고 있는 간선이 사이클을 형성한다면 최단 경로가 무한히 음수가 될 가능성이 있다는 것이다. 벨만 포드는 이러한 음의 사이클을 잡아낼 수 있는 알고리즘이다. 하지만 시간 복잡도가 O(VE)로 다익스트라 알고리즘에 비해 느리다는 단점이 있다.

 

INF = int(1e9)

v, e = map(int, input().split())
graph = []
distance = [INF] * (v + 1)

# 모든 간선의 정보 입력
for _ in range(e):
    a, b, c = map(int, input().split())
    graph.append((a, b, c))

def bellman_ford(start):
    distance[start] = 0
    for i in range(v):
        for j in range(e):
            cur_node = graph[j][0]
            next_node = graph[j][1]
            edge_cost = graph[j][2]
            if distance[cur_node] != INF and distance[next_node] > distance[cur_node] + edge_cost:
                distance[next_node] = distance[cur_node] + edge_cost
                if i == v - 1:
                    return True

    return False