벨만-포드 알고리즘(11657 타임머신)

벨만-포드 알고리즘

다익스트라와 마찬가지로 SSP알고리즘인 벨만-포드 알고리즘은 음의 가중치를 다룰 수 있다.

그런데 다음과 같이 음의 가중치로 인해 순환 구조를 가진다면 최단경로를 구할 수 없다.

따라서 벨만-포드 알고리즘은 최단경로를 구하는 것과 이 그래프에서 최단경로를 구할 수 있는지 없는지를 판별하는 과정 두 과정으로 나눠진다.

벨만 포드 알고리즘은 V-1번 모든 간선을 Relax하는 작업을 수행한다.

 

최단경로구하기

동작과정은 각 정점들을 돌아 가면서 모든 간선들을 탐색한다, 단 맨 처음은 시작점부터 탐색한다( 처음 이후에는 순서 상관없음)
D(s,v)=D(s,u)+w(u,v)

 

이 과정을 V-1번 탐색하는 이유는 s에서 v까지 가는 경우에서 v를 뺀 모든 경로가 각각 최단거리일 수 있기 때문이다(최악의 경우).따라서 v-1번을 해주는 것이다.(그림으로 이해하려면 맨 밑 주소로 가보자)

v-1번

 

음의 가중치로 인한 순환 구조 확인

위의 그림처럼 2와 -4로 이어진 순환구조가 있다면 마이너스가 계속 늘어나므로 최단경로를 구할 수 없다.

이것을 확인하는 방법은 한번 더 모든 간선을 돌아보면 해결된다. v-1번까지 돌았을 때 정상 그래프라면

모두 최단거리로 설정되있을텐데 한번 더 relax할 때 값이 바뀌는 부분이 있다면 순환구조가 생긴 것이다.

코드로 쉽게 구현할 수 있다.

 

따라서 시간복잡도는 간선의 갯수e와 정점의 갯수 v를 곱한 O(VE)이다

코드를 구성할 때는 무한대로 초기화 되있는 곳은 방문한적 없는 곳이므로 손대지 않고 continue해준다.

 

11657 타임머신

https://www.acmicpc.net/problem/11657

1.접근

음의 경로가  포함되있는 최단경로를 구하는 문제이므로 벨만-포드 알고리즘을 사용한다.

2.풀이

시작지점이 1로 고정되어있으므로 ans배열을 INF들로 초기화 시킨후 ans[1]=0으로 초기화해준다.

이제 n-1번 만큼 반복하면서 정점으로 부터 모든 간선을 돌아주는 3중 for문을 만든다.

값들을 relax해갈 때 배열의 값이 INF면 방문하지 않았던 곳이므로 continue해준다.

이 과정을 해주지 않으면

예를 들어 INF>INF-2 때문에 배열값이 엉망이 될 수 있다.

이렇게 v-1번 돌고 마지막 한번더 반복하여 값이 바뀌면 -1을 바로 출력하고 종료한다.

(이 때 INF값 continue를 안해줘서 틀렸었다)

3.코드

4.배운점

• 음의 가중치가 보이면 벨만-포드를 떠올리자
• 정점의 갯수가 V일 때 V-1번인 이유를 기억하자
• 사실 따로 순환구조를 for문 한번더 만들어서 코드로 길게 확인하는 것보다 v-1번이 아닌 v번을 돌아서 v번째 과정에 바뀌는 값이 있으면 -1을 반환하는 좀 더 짧은 코드를 구현할 수 있다.

 

v-1번 돌아야하는 이유

https://sodocumentation.net/ko/algorithm/topic/4791/%EB%B2%A8%EB%A7%8C-%ED%8F%AC%EB%93%9C-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

공부한 곳https://victorydntmd.tistory.com/104?category=686701