Bellman Ford Algorithm

https://tose33.tistory.com/830

백준 11657. 타임머신

 

 

 

Dijkstra 알고리즘은 하나의 정점에서 다른 모든 정점까지의 최소 비용을 구한다.

하지만 다익스트라 알고리즘은 음의 가중치가 있으면 사용할수 없다. 

그리디하게 현재 노드에서 가장 최소 가중치를 선택하기 때문이다.

 

Bellman Ford 알고리즘은 다익스트라 알고리즘과 비슷하게 하나의 정점에서 다른 정점까지의 최소 비용을 구하는데 음의 가중치가 있어도 사용 가능하다.

정확히 말하면 벨판 포드는 그래프에 음의 사이클이 있는지 없는지 판별하는 알고리즘이다. 

 

음의 싸이클 있는지 판별하는 법: 

정점의 갯수가 N일때, N-1번 탐색하고 N번째 탐색에서도 변경이 일어나면 음의 사이클이 존재하는 것이다. 

 

 

알고리즘이 작동 하는 방법은

1. 모든 간선들에 대하여, 간선의 출발점이 한번이라도 탐색된 정점이라면 해당 간선을 타고 도착한 정점의 거리를 업데이트한다.

2. 1번 과정을 N-1 번 반복한다. 

3. 한번더 반복해서 (즉 N번째 반복) N-1번 반복했을때와 달라지는 거리 값이 있다면 음의 사이클이 존재한다는 뜻이다.