벨만 포드 알고리즘
벨만 포드 알고리즘
다익스트라는 가중치가 음수가 아닌 경우 특정 노드까지 이동하는 최소 비용의 경로를 찾는 알고리즘이였다. 벨만 포드는 음수의 가중치도 허용한다.
대신 다익스트라의 시간복잡도가 O(간선 수 * log 정점 수) 였다면 벨만 포드의 시간복잡도는 O(간선 수 * 정점 수) 로 더 느린 알고리즘이다.
플로우
시작 정점과 도착 정점이 정해져있을 때 사용하는 알고리즘이다.
동작원리를 설명하기 앞서 한 가지 정보를 알아야한다.
N 가지 정점이 있고 어느 한 정점에서 다른 정점으로 가는 최단거리를 구하기 위해선 최대 N-1 의 간선만 거치면 된다.
시작 정점이 1일 때 3 (N-1) 이내인 1 거리만에 모든 정점 과의 최소 비용 거리를 알아낼 수 있다.
마찬가지로 제일 멀리 떨어진 정점도 3 (N-1) 이내인 3 거리로 최소 비용 거리를 알 수 있다.
한 정점은 반드시 다른 정점으로 이어질 것이고 N-1 의 간선을 이동하고도 찾지 못한다면 그건 애초에 이어질 수 없는 정점이거나 중간에 음의 가중치 사이클에 의해 무한히 값이 음의 무한으로 수렴하는 경우일 것이다.
양의 가중치 사이클에 의해 N-1 을 초과할 수 있지 않냐 생각할 수도 있는데 사이클이 어느 한 정점에 중복적으로 접근한다는 개념이니 양의 가중치 사이클의 경우 이전 접근보다 비용이 필히 높아질 것이니 중복적으로 접근하지 못하도록 구현된다. 그러니 최소 비용 거리를 고려할 때 양의 가중치 사이클은 고려하지 않아도 괜찮다.
기존 다익스트라 방식으로 음의 가중치를 만나게 되면 잘못된 결과를 얻을 수 있다.
시작 정점이 1 이고 도착 정점이 4 일 때 기존 다익스트라 알고리즘에선 1 -> 2-> 4 의 경로로 최소 비용을 3이라 하겠지만
실제로는 1 -> 3 -> 4 의 비용 -95 가 정답이다.
그리디한 접근은 끝판에 가서 뒤집힐 수 있으니 모든 수를 다 봐야한다. 그래도 우린 못해도 N-1 번만 하면 최소 비용 경로를 구할 수 있다는 힌트를 알고있다.
그래서 벨만 포드 메인 로직에 들어가자면
N-1 번 반복하며 모든 간선에 다음을 검사하고 적용하는 것이다.
- 시작 정점에서 현재의 간선을 이용할 수 있는가?
- 1을 만족할 시 현재 간선에서 도착 정점에 대한 비용의 크기 비교를 통해 더 작은 값으로 바꾼다.
아래 소스 코드에선 N 번 반복한다. 이는 음의 사이클을 판별하기 위한 방법이다. N-1 번 반복을 한 다음 N 번 째일 때도 더 작은 값이 나와 변화가 생긴다면 그건 분명 음의 사이클이 있어 무한히 음의 무한대로 수렴시키기 때문이다.
소스 코드
BOJ 11657 문제의 답이기도 하다.
n, v = map(int, input().split())
INF = float("inf")
edges = []
for _ in range(v):
s, d, c = map(int, input().split())
edges.append((s, d, c))
dist = [INF] * (n+1)
dist[1] = 0
for turn in range(n):
for e in edges:
s, d, c = e
if dist[s] == INF or dist[d] <= dist[s] + c: continue
if turn == n-1:
print(-1)
exit()
dist[d] = dist[s] + c
for i in dist[2:n+1]:
print(i if i != INF else -1)시작 정점에서 현재의 간선을 이용할 수 있는가는 if dist[s] == INF 조건부에서 확인할 수 있다.
현재 간선의 출발점이 INF 가 아니라면 이전에 시작점에서 연결된 적 있는 간선에 의해서 연결된 정점이란 의미이다. (시작점과 출발점을 구분하였다. 출발점은 각 간선마다 출발하는 정점 코드 내에서는 for 문 내의 s 변수이다. 시작점은 그래프 전체를 보았을 때 시작되는 정점이다. 코드 내에서는 1 이 시작점임을 확인할 수 있다.)
이후 기존 값보다 작은 경우에만 변화를 주며 전체 경우에 접근하면 된다.