벨만 포드 알고리즘 - 백준 11657 (22.7.17)

사용자가 특정 차트를 고르면, 전 종목의 과거(10년) 차트들을 모두 탐색하여 가장 유사한 차트 10개를 골라 사용자에게 보여줍니다.

 

웹프로젝트 링크

비슷한 차트 검색기

 

 

벨만 포드 알고리즘이란

 

벨만 포드 알고리즘(Bellman-Ford Algorithm)은 한 노드에서 다른 노드까지의 최단 거리를 구하는 알고리즘이다.

 

다익스트라 알고리즘이 모든 가중치가 양수인 경우에만 사용할 수 있는 반면에 벨만-포드 알고리즘은 노드 간의 간선 가중치가 음수인 경우에도 사용할 수 있다.

 

벨만 포드 알고리즘의 동작

1. 시작 노드를 설정한다.
2. 시작 노드에서 각 다른 노드의 거리 값을 무한대로 설정하고 시작 노드를 0으로 설정한다.
3. 현재 노드의 모든 인접 노드를 탐색하며 기존에 저장된 인접 노드까지의 거리보다 현재 노드를 거치고 인접 노드에 도달하는 게 더 짧을 경우 값을 경신한다.
4. 3의 과정을 모든 노드에 대해 수행한다.
5. 모든 노드에 3 - 4를 수행하고서 또 거리가 갱신된다면 −∞
   를 발생시키는 음수 사이클이 존재함을 의미한다.

 

음수 사이클의 문제점

• 사이클이 존재하나 양수값이 더 클 경우 : 사이클을 순환하여도 이득이 없으므로 그대로 진행한다.
• 사이클이 존재하고 음수값이 더 클 경우 : 사이클을 순환할수록 가중치가 감소해 최소 비용을 찾는 입장에서 사이클을 무한히 순환하고 목적지에 도착함은 실질적인 최단 경로라 보기 어렵다. 적어도 동일 노드를 방문하면 안 된다는 등 제약 조건이 있어야 한다.

 

음수 사이클의 존재 여부 검출

 

V - 1번만큼 탐색을 마쳤으므로 최단 거리 제약 한계에 도달했다. 이다음 순회에서도 만약 갱신되는 값이 존재한다면 앞으로도 계속 갱신됨을 의미하므로 음수 사이클이 존재함을 의미한다.

 

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

 

우선 $|V|−1$번만큼 순회하므로 O(V)가 되고 매번 총 edge(O(E))만큼 탐색하므로 O(|V||E|)가 된다.

 

그런데 모든 노드에 간선이 연결되어 있다면 라면 E는 V^2에 근사해지므로 최악의 경우 O(V^3)이 된다. 이는 다익스트라 알고리즘이 최악의 경우 O(V^2)인 것과 비교했을 때 불리함을 알 수 있다. 따라서 벨만-포드 알고리즘은 간선의 가중치에 음수가 존재할 경우에만 채택해야 한다.

 

 

 

 

백준 11657번 문제

 

음의 간선이 존재하는 그래프 내에서 최단 경로를 찾는 벨만-포드 알고리즘을 활용하여 풀 수 있는 문제이다.

 import sys
input = lambda : sys.stdin.readline().rstrip()
INF = 987654321

N, M = map(int, input().split())
edges = []
distance = [INF] * (N + 1)
for _ in range(M):
    edges.append(tuple(map(int, input().split())))

def bf(start):
    distance[start] = 0 # 시작 노드에 대해서 거리를 0으로 초기화
    for i in range(N): # 정점 수만큼 반복
        for j in range(M): # 매 반복 마다 모든 간선 확인
            now, next, cost = edges[j]
            # 현재 간선을 거려서 다른 노드로 이동하는 거리가 더 짧은 경우
            if distance[now] != INF and distance[next] > distance[now] + cost:
                if i == N - 1:
                    return True # n-1번 이후 반복에도 값이 갱신되면 음수 순환 존재
                distance[next] = distance[now] + cost
    return False

if bf(1):
    print(-1)
else:
    for i in range(2, N + 1):
        print(distance[i] if distance[i] != INF else -1)