벨만-포드 알고리즘(Bellman-Ford Algorithm)

첫번째 반복으로 최단경로를 구했다면, 다음 음의 사이클이 G 내부에 존재하는지 판정하는 두번째 반복

두 번의 반복으로 G 에서 시작정점 V_start - 도착정점 V_end 최단경로 혹은 내부에 음의사이클 존재 여부를 확인할 수 있다.

반복을 하기전 초깃값을 설정해야한다.
정점이 n 개
간선이 m 개 존재한다고 가정하자.

가정1) 이때 정점A에서 정점B 로 이르는 간선은 무조건 존재한다고 하면,
사이클이 존재하지 않는다면, 최대 몇개의 간선을 가질 수 있을까?
이는 n-1 개 , 즉 """정점의 수 - 1""" 개를 가질 수 있다.
처음에 이 말이 잘 이해가 가지 않았는데...
생각해보니 너무나 당연한 말이었다.

 

위 그림에서 총 8개의 정점이 존재한다.
최대한 돌아서 사이클이 없이 1에서 8까지 이동한다고 하면?

 

위와 같이 그리거나 또 다르게 그릴 수 있을 것이다. 
그런데 결론적으로 7개의 간선 밖에 그리지 못할 것이다. 
그렇기 때문에 정점1에서  정점8까지 이르는 간선의 최대수는 n-1개 ; 정점의 개수-1 일 수 밖에 없다.

이것이 첫번째 반복의 키가 된다.

벨만포드 알고리즘은 시작정점을 고르고, 어떤 정점까지 이르는 거리를 구한다. 
(=시작정점부터 - 시작정점을 제외한 모든 정점까지 이르는 거리를 구함) 

시작정점A에서 어떤 정점까지 이르는 간선의 수는 N-1 개 이기 때문에, 시작정점의 초깃값을 설정하고 모든 간선을 N-1번 돌며, 각 정점에 이르는 거리를 갱신시키면 된다.

그렇다면 초깃값 설정은?
1) 시작정점의 초깃값을 설정한다.
2) 시작정점을 제외한 모든 정점은 무한대(INF) 혹은 -무한대(-INF)로 설정할 수 있다. (문제나, 코드를 작성하는 사람에 따라 다르니...)

위와 같은 그래프 G 가 존재한다고 할 때, 
시작을 정점1 로 설정하며, 다른 정점으로 이르는 거리가 최소가 되는 것을 구한다면,
여기서 초깃값 설정은 시작정점 / 시작정점 외 정점들 의 비용을 잡아 줘야 한다.

1) 시작정점(정점1) : 0
2) 시작정점을 제외한 정점 : INF

 

그리고 나서 낮은 번호 정점부터 시작하여 정점에서 다른 정점으로 나가는 간선을(출발->도착 인 간선) 으로 도착정점을 갱신을 해준다. 
이것을 N-1 ; 정점의 개수 - 1 번 갱신해야 한다.

그렇다면 5개의 정점이므로 , 4번의 갱신을 해야한다는 의미가 된다.

이때 갱신의 기준은 
출발정점 의 비용 V[here]
도착정점 의 비용 V[there]
Here -> There 로 이르는 간선의 비용 : cost

if( V[there] > V[here] + cost && 
     V[here] != INF)
총 두 개의 조건을 모두 충족해야 갱신을 한다. 

1) V[there] > V[here] + cost 
현재 도착정점(V[there])까지 갱신된 비용보다 
현재 출발정점(V[here])에서 해당 간선으로 이동하는 비용( cost ) 이 더 작다면 갱신을 시킨다. 
최단거리를 구하는 것이니 당연하다.
2) V[here] != INF 
현재 출발정점의 비용이 무한대인 경우는 제외한다. 왜냐하면 음의 가중치를 갖는 간선을 가진 유향 그래프(G)이기 때문이다. 
V[there] 가 INF 인 경우 V[here] 도 INF 라면, 이때 cost의 비용이 -1 일 경우에
V[there] > V[here] + cost
INF > INF - 1 이기 때문에 갱신을 시키게 된다. 
그렇기 때문에 위 경우를 제외시켜야 한다.

이제 첫번째 반복을 시작한다.

한번의 반복만으로 시작정점 1 에서 부터 다른 정점까지 이르는 최단거리가 모두 갱신되었지만, 그래프의 모양은 어떻게 주어 질 지 알 수 없다는 가정을 하면 N-1번 반복을 해야한다.

이제 두번째 반복 - 음의 사이클 유무의 판정을 한다. 

두번째 반복은 
음의 사이클은 모든 간선을 한 번 더 순회하며, 갱신될 수 있는 정점이 존재하면? 
음의 사이클이 존재한다는 의미이다.

 

 

 

정점 4에서 정점 3으로 이르는 간선을 추가하였다. 눈으로 봐도 3->5->4->3->.... 사이클이 존재한다. 이때 사이클을 계속적으로 돌게 되면 값이 -3씩 감소하게 된다는 것을 알 수있고, 나머지 정점2 또한 계속해서 작은 값으로 갱신될 수 있다. 

첫번째 반복을 모두 시행하고, 각 정점에 이르는 비용이 정해졌다고 하자.

 

 첫번째 반복으로 각 정점에 이르는 비용이 
정점2 : A
정점3 : B
정점4 : D
정점5 : C
로 갱신이 완료된 상태일 때

두번째 반복을 시행하게 되면, 음의 사이클이 존재하므로 
if(V[there] > V[here] + cost && V[here] != INF) 인 갱신을 위한 조건문을 사용해서, 조건이 True 인 것이 존재한다면? 
위 그래프는 음의 간선이 존재하는 것이다. 
순서대로 따라가보면

정점 1 -> 정점 2로 가는 간선은 갱신이 일어나지 않는다.

아 이렇게 설명하면 안되는데.. 정점 2에서 정점 3 이르는 간선으로 갱신이 일어날 수도 있고, 안 일어 날 수도 있다고 판단된다. 

 정점 3에서 정점 5로 이르는 간선은 정점 5를 갱신을 시키게 된다. 
왜냐하면 
첫번째 반복으로 
B의 값은 D+1 의 값을 갖게 되었고, 
C의 값은 D-1 값을 가졌을 것이다. 
그렇다면 B는 V[here] / C 는 V[there] / cost 는 -5 이므로 
D-1 > D+1 - 5 이므로 / D-1 > D-4 가 되며, 갱신을 할 수 있는 조건이 된다. 
그렇기 때문에 음의 사이클 판정을 할 수  있다. 

요약을 하자면,

0. 초깃값 설정을 한다. (시작정점 / 시작정점외 정점들)
1. 첫번째 반복을 한다. 최단거리를 찾기위함. (정점의개수-1 번 (모든간선 순회) ) 
2. 두번째 반복을 한다. 음의사이클 판정하기 위함.

으로 정리된다.

벨만-포드 알고리즘에 대한 문제로 
BOJ-11657 타임머신 문제가 있다. 
코드는 위 문제의 코드와 동일하므로 따로 첨부하지 않음.

 

 

 http://wondy1128.tistory.com/56