알고리즘 유형 : 최단경로(벨만포드)
풀이 참고 없이 스스로 풀었나요? : X
https://www.acmicpc.net/problem/11657
소스 코드(파이썬)
import sys
sys.stdin = open("input.txt", "rt")
input = sys.stdin.readline
INF = sys.maxsize
N, M = map(int, input().split())
roadmap = []
for _ in range(M):
A, B, C = map(int, input().split())
roadmap.append((A, B, C))
# 벨만 포드 알고리즘
def bellman_ford(start):
distance = [INF]*(N+1)
distance[start] = 0
for step in range(N):
for edge in roadmap:
start_city = edge[0]
end_city = edge[1]
time = edge[2]
cal_d = distance[start_city] + time
if distance[start_city] != INF and cal_d < distance[end_city]:
distance[end_city] = cal_d
if step == N-1:
return -1
return distance
result = bellman_ford(1)
if result == -1:
print(-1)
else:
for i in range(2, len(result)):
c = result[i]
if c == INF:
print(-1)
else:
print(c)
풀이 요약
- 벨만 포드 알고리즘을 그대로 구현하기만 하면 되어서, 벨만 포드 알고리즘 학습에 용이한 문제이다.
- 벨만 포드 알고리즘도 다익스트라와 똑같이 출발 노드에서 모든 노드까지의 최단 거리를 구하는데, 차이점은 가중치가 음수인 경우도 가능한 것이다.
-
어떻게 음수인 경우에도 가능할까.
우선 다익스트라는 그리디스럽게 바텀업 방식으로 최단거리를 갱신해나간다. 매 단계에서 인접 노드 중 출발 노드로부터 가장 거리가 짧은 노드를 우선으로 탐색한다. 이 때 다익스트라 알고리즘은 한 번 방문했던 노드는 다시는 방문하지 않는 특성이 있는데, 이로 인해서 그리디스럽게 탐색을 이어나가더라도, 어떤 가중치가 음수라면 그 루트를 통해 해당 노드에 재방문하여 최단거리가 새롭게 갱신되는 경우가 존재하므로, 다익스트라로는 가중치가 음수인 경우에는 최단거리를 구하는데 애로사항이 생긴다.
반면 벨만 포드 알고리즘은 다익스트라와 똑같이 모든 노드를 방문하긴 하는데, 모든 노드에 대해서 실행하는 내용이 "모든 간선에 대하여 최단거리 갱신 시도"이라는게 차이점이다.
출발 노드의 최단 거리를 0으로 잡고, 이 후 노드 개수 V에 대해 V-1번만큼 모든 간선에 대해 업데이트할 게 있으면 업뎃해주는 기능을 실행한다.
즉, 첫 번째 시도에서 만약 2 -> 3번 간선으로 3번의 최단 거리를 업뎃했을 때, 두 번째 시도에서 또 다른 루트. 예를 들어서 4 -> 3과 같은 간선에 의해 3번이 한번 더 갱신될 수 있는 것이다. 다익스트라의 경우에는 한 번 갱신된 노드는 다시 갱신될 수 없다.
이런 원리로 가중치에 음수가 존재한다면, 음수 가중치를 거쳐서 도달하는 루트가 최단 경로인 케이스까지도 모두 고려해줄 수 있는 것이다.
-
그렇다면 왜 모든 간선 업뎃(edge relaxation)을 노드의 총 개수인 V에 대해 V-1번 해주는 걸까?
그 이유는, 만약 정말 업뎃이 운이 없어서 가장 느리게 되는 노드가 있다고 치면, 이 노드는 최악의 경우 V-1번 모든 간선을 탐색해야 최단 거리를 확정지을 수 있다.
예를 들어, 1~4번 노드가 있다고 치자.
그리고 1 -> 2 -> 3 -> 4 이렇게 그래프가 있다고 치고 각 간선의 가중치가 왼쪽부터 [2, 4, 3] 이라고 치면,
최단 거리 리스트는 [0, INF, INF, INF] 이렇게 되어있을 것이다.
여기서 참고할 내용이 있는데, 벨만 포드 알고리즘은 모든 간선 업뎃을 수행할 때, 간선의 출발 노드의 최단 거리 값이 INF인 경우는 건너뛴다. 갱신할 때 도착 노드의 최단거리 값과 (출발 노드 최단거리 + 간선 가중치)값을 비교하는데, 후자의 값이 INF+w가 되어버리므로 업뎃이 불가능하다. 따라서, 출발 노드가 INF이면 그 간선에 대해서는 업뎃을 수행하지 않고 건너뛴다.
자 이제 살펴보자. 만약 1부터 4까지의 최단거리를 구하고자 할 때 최악의 경우로 업뎃을 수행해보자.
그래프 : 1 -> 2 -> 3 -> 4
가중치 : 2, 4, 3 (왼쪽 간선부터)우선 for문에서 최악의 순서로 3 -> 4, 2 -> 3, 1 -> 2 순서로 간선 업뎃을 수행했다고 해보자.
그럼 최단 거리 리스트는 [1, 2, INF, INF]가 될 것이다.
그 다음 최악의 순서로 모든 간선 업뎃을 마찬가지로 수행해주면
[1, 2, 4, INF]
그 다음 또 세 번째 수행을 해주면
[1, 2, 4, 3]으로, 1에서 4로 가는 최단거리를 구할 수 있게 된다.여기서 모든 간선 업뎃은 총 노드의 개수 4에 대해 4-1 = 3번 수행했다.
즉 모든 간선 업뎃을 V-1번 실행하면 모든 노드에 대해 반드시 최단거리를 구할 수 있음을 알 수 있다.
-
그런데 음의 사이클이 존재하는 경우를 고려해줘야한다.
음의 사이클이 존재하지 않는다면 V-1번 수행했을 때 모든 노드 최단거리를 확정지을 수 있는게 맞다.
그러나 음의 사이클이 존재한다면 음의 사이클을 거쳐서 도착할 수 있는 모든 노드의 최단 거리 값이 무한대가 된다.
즉, 벨만 포드 알고리즘으로는 그 노드들의 최단 거리를 정할 수 없게되는 것이다.
그래서 이런 경우에 확정이 불가하다고 False를 의미하는 값을 리턴하도록 함수를 작성할 수 있는데,
모든 간선 업뎃(edge relaxation)을 V번 째로 한번 더 수행했을 때 최단 거리가 하나라도 업데이트된다면, 그 것이 곧 음의 사이클이 존재한다는 뜻이므로 이를 판별해내어 False를 의미하는 원하는 값을 리턴해낼 수 있다.
배운 점, 어려웠던 점
- 벨만 포드 알고리즘에 대해 학습할 수 있는 문제였다.
- 다익스트라와의 차이점, 벨만 포드 알고리즘 원리 자체에 대한 이해 등이 많이 어려워서 애를 먹었다.
