11657번: 타임머신
첫째 줄에 도시의 개수 N (1 ≤ N ≤ 500), 버스 노선의 개수 M (1 ≤ M ≤ 6,000)이 주어진다. 둘째 줄부터 M개의 줄에는 버스 노선의 정보 A, B, C (1 ≤ A, B ≤ N, -10,000 ≤ C ≤ 10,000)가 주어진다.
www.acmicpc.net
아이디어:
벨만-포드 알고리즘을 이용하여 최단경로를 구해야한다. 다익스트라 알고리즘은 간선의 가중치가 음수인 경우에는 사용하지 못하기 때문이다. 벨만-포드 알고리즘의 시간복잡도는 O(VE)이다.
벨만 - 포드 알고리즘은 존재하는 모든 간선을 V-1번 돌아보면서 이 간선을 통할 수도 있는 최단경로들의 거리를 갱신하는 것이다. 왜 V-1번 이냐면 최단 경로가 되려면 최대 V-1개의 간선을 통과하기 때문이다. 하지만 여기서! 이 문제처럼 음의 가중치를 가지고 있고, 음의 사이클이 가능한 벨만-포드 문제에서는 음의 사이클을 찾기 위해서 V번 돌아봐야 한다. 음의 사이클이 없다면 마지막 V번째에서 최단 거리가 갱신되지 않을 것이지만, 만약 음의 사이클이 존재한다면 V번째에서 최단 거리가 갱신될 것이기 때문이다.
m.blog.naver.com/kks227/220796963742
(참고)
구현하는 방법은 어렵지 않다. 그래도 아직 익숙하지 않으니 익숙해지려면 좀 더 많이 풀어봐야 할 것 같다. 시간복잡도는 다익스트라 알고리즘이 더 효율적이지만, 음수 가중치가 있는 경우에는 벨만-포드 알고리즘을 사용해야 한다!
import sys
N,M = map(int, sys.stdin.readline().split())
graph = [[] for _ in range(N+1)]
for _ in range(M):
A, B, C = map(int, sys.stdin.readline().split())
graph[A].append([B,C])
INF = 10**9
dist = [INF]*(N+1)
dist[1] = 0 #시작 정점
flag = False #음수 사이클 판단
for i in range(1,N+1): #모든 정점에 연결되어 있는 간선 N번 탐색
for j in range(1, N+1):
if (dist[j]==INF): continue #연결되지 않은 정점은 패스
for adj in graph[j]:
if (dist[j]+adj[1] < dist[adj[0]]):
if (i==N):
flag = True #N번째에 최단경로 갱신되면 음수 사이클존재하는것
dist[adj[0]] = dist[j]+adj[1]
if (flag == True):
print(-1)
else:
for i in range(2,N+1):
if (dist[i]==INF): print(-1)
else: print(dist[i])
'알고리즘💻 > 벨만포드&플로이드와샬' 카테고리의 다른 글
BOJ 11780번: 플로이드 2 (0) | 2021.02.15 |
---|---|
BOJ 11404번: 플로이드 (0) | 2021.02.15 |
BOJ 11403번: 경로 찾기 (0) | 2021.02.15 |
BOJ 1389번: 케빈 베이컨의 6단계 법칙 (0) | 2021.02.15 |
BOJ 1865번: 웜홀 (0) | 2021.02.15 |