[알고리즘] 벨만포드, 그것이 알고싶다

오늘은 저번에 이어서, 

최단경로 알고리즘 중 하나인 

벨만-포드 알고리즘

을 같이 알아볼까요

---

 

# 벨만-포드 알고리즘

최단 경로 알고리즘 중 하나로, 한 노드에서 다른 노드까지의 최단거리를 구하는 알고리즘입니다.

간선의 가중치가 음수일 때에도 최단거리를 구할 수 있다는 장점이 있습니다.

 

다익스트라 vs 벨만-포드

• 다익스트라
  • 아직 방문하지 않은 노드들 중 최단 거리가 가장 짧은 노드를 선택
  • 음의 가중치가 없을 때만 가능!
  • 시간이 벨만포드에 비해 빠름
• 벨만포드
  • 매 단계마다 모든 간선을 확인하면서 최단 거리를 찾음
  • 음의 가중치가 있더라도 최단 거리를 찾을 수 있음
  • 시간이 비교적 느림

 

 

# 문제로 이해해보기

간단한 벨만포드 문제인 백준 11657번 타임머신 문제를 한번 풀어보면서 이해해 봅시다.

각각의 도시가 있고, 도시를 지나는 버스 노선이 있습니다. 각 버스 노선별로 걸리는 시간이 다른데, 이 때 시간이 음수일 수도 있으므로 다익스트라가 아닌 벨만포드로 푸는 문제입니다.

첫번째 테스트 케이스를 이용해서 문제를 한번 풀어볼까요

첫번째 테스트케이스

다음과 같은 상황의 문제입니다. 

 

우선 처음으로 출발지가 1번 도시라고 했을 때, 1번 도시와 각 도시까지의 거리를 무한대(∞)로 놓고 최단거리를 구합니다.

초기 단계

 

첫번째로 버스를 한 개만 탔을 때의 최단 거리를 각각 저장해줍니다.

노란색으로 체크된 부분이 한번만 이동한 경로이고, 각각의 최단거리는 4와 3으로 업데이트 됩니다.

 

이후 버스를 2번 탔을 때의 최단 거리를 업데이트 해줍니다.

파란색 체크된 부분이 버스를 두번 탔을 때 이동한 경로입니다. 1 → 2 → 3으로 갈때 4 + ( -1) 이므로 기존의 3과 똑같이 때문에 업데이트 하지 않습니다.

또한 1 → 3 → 1로 가는 것도 3 + (-2)  > 0이므로 업데이트 하지 않습니다.

 

 

이런식으로 N - 1번(도시의 갯수 - 1)만큼 확인을 하고, 마지막으로 N번 시행했을 때, 값이 업데이트 되는지를 확인합니다.

예를 들어, 2번 도시 기준으로 3번 시행하면 다음과 같은 사이클이 만들어집니다.

1 → 2로 바로가는게 4,

1 → 2 → 3  →1 →2 로 가는 것이 5가 되므로 값이 업데이트 되지 않습니다

이렇게 N번 시행했을 때 값이 업데이트 되지 않는다면 음수 사이클이 없는 것을 확인할 수 있습니다.

 

 

위 문제의 2번 사이클의 경우,

1 → 2로 바로가는게 4,

1 → 2 → 3  →1 →2 로 가는 것이 2, 

한바퀴 더 돌면 0 ....

즉, 계속 값이 업데이트 되면서 음수사이클이 발생함을 알 수 있습니다.

 

 

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

벨만포드 알고리즘은 위의 상황과 같이 매 단계마다 모든 간선을 확인하며 노드간의 최단거리를 구하기 때문에

O(VE)의 시간 복잡도를 가집니다.

비교적 느린편이지만 음의 가중치를 가질 때에도 활용할 수 있기 때문에 알아두면 아주 좋은 알고리즘입니다!

 

 

---

# 파이썬으로 구현해보기

N, M = map(int,input().split())
# 간선 정보 리스트
bus = []
# 최단거리 저장할 리스트
dis = [float('inf') for _ in range(N + 1)]
dis[1] = 0      # 시작점은 거리 0

for _ in range(M):
    a, b, c = map(int,input().split())
    bus.append((a, b, c))

# 음수사이클 판별용
isNegativeCycle = False

# 벨만포드알고리즘
for i in range(N):
    # 모든 간선을 체크
    for j in range(M):
        now, next, cost = bus[j]
        # 지금이 무한이 아니고, 현재에 cost 더한게 저장되어있는거보다 작다면 업데이트
        if dis[now] != float('inf') and dis[next] > dis[now] + cost:
            dis[next] = dis[now] + cost
            # 음수사이클 판별용, N - 1번째에도 업데이트가 되었다면,
            if i == N - 1:
                isNegativeCycle = True

if isNegativeCycle:
    print(-1)
else:
    for idx in range(2, N + 1):
        if dis[idx] != float('inf'):
            print(dis[idx])
        else:
            print(-1)

 

 

 

---