우리는 이미 이전 포스팅에서 최단 경로(거리) 문제의 대표적인 알고리즘인 다익스트라 알고리즘에 대해 배웠다. 다익스트라 알고리즘의 특징 중 하나는 음의 간선이 없을 때만 정상 동작한다는 것이다. 그렇다면 간선이 음의 비용을 갖고 있다면 어떻게 최단 경로를 알아낼 수 있을까? ( 다익스트라 알고리즘을 모른다면 이전 포스팅을 보고 오는 것을 추천한다 🤗 )
백준의 타임머신 문제를 보면 특정 도시에서 다른 도시를 이동할 때 걸리는 시간이 양수가 아닌 경우가 있다. 순간 이동을 하는 경우는 시간을 0으로, 또 타임머신을 타고 이전으로 돌아가는 경우는 시간이 음수값이 되기도 한다. 이러한 상황이 음의 간선이 포함되었을 때 최단 경로를 구하는 문제 예시 중 하나라고 볼 수 있다.
위 그림을 보면 음수 간선이 포함되어 있더라도 우리가 이미 알고있는 다익스트라 알고리즘 동작 과정을 통해 1번 노드로부터 시작되는 각 노드들의 최단 거리 (최소 비용)을 구할 수 있다.
하지만 간선 정보에 따라 최소 비용을 결정하지 못하는 경우도 존재하는데, 그 예가 바로 위 그림의 경우이다. 우리는 파란 선으로 되어있는 음수 간선의 사이클을 통해 비용을 무한히 줄여나갈 수 있다. 결국 음수 간선 사이클이 발생하면 최소 비용을 결정짓지 못하고 최소 비용이 음의 무한값으로 빠지게 된다. 이렇게 되면 궁극적으로 다익스트라 알고리즘을 음의 간선이 있는 그래프 전체에 적용시킬 수 없다.
먼저 최단 경로 문제는 다음과 같은 상황에 따라 분류하여 생각해볼 수 있다.
O(EV)
이므로 다익스트라 알고리즘의 시간복잡도인 O(ElogV)
보다 느리다 (그래서 보통 모든 간선이 양수인 경우에는 성능을 위해 다익스트라 알고리즘을 쓰는 것이 낫다)n-1
번 반복한다.import sys
input = sys.stdin.readline
INF = int(1e9)
n, m = map(int, input().strip().split())
edges=[]
distance=[INF]*(n+1)
for _ in range(m):
a, b, c = map(int, input().split())
edges.append((a, b, c))
def bf(start):
distance[start]=0
for i in range(n):
for j in range(m):
cur_node= edges[j][0]
next_node= edges[j][1]
cost= edges[j][2]
if distance[next_node] > distance[cur_node]+cost:
distance[next_node]=distance[cur_node]+cost
if i==n-1:
return True
return False
negative_cycle=bf(1)
if negative_cycle:
print(-1)
else:
for i in range(2,n+1)
if distance[i]==INF:
print(i,'까지의 최단 거리:도달불가')
else:
print(i,'까지의 최단 거리:',distance[i])
정리가 잘 된 글이네요. 도움이 됐습니다.