벨만포드 알고리즘

• 다익스트라, 플로이드-워셜과 함께 가장 많이 사용되는 “최단경로 알고리즘” 3가지 중 하나.

• V개의 정점과 E개의 간선을 가진 가중 그래프 G에서 특정 출발 정점(S)에서 부터 다른 모든 정점까지의 최단경로를 구하는 알고리즘

---

1. 핵심 IDEA

V개의 정점과 E개의 간선을 가진 가중그래프에서 어떤 정점 A에서 어떤 정점 B까지의 최단거리는 최대 V-1개의 간선을 사용한다. 즉, 시작 정점 A를 포함하여 최대 V개의 정점을 지난다.

2. 특징

• 일반적으로 다익스트라 알고리즘보다 느리고 플로이드-워셜 보다는 빠른 중간정도의 연산속도를 같는다.

• 다익스트라 알고리즘과는 달리 음의 가중치를 갖는 간선을 포함하는 그래프에서도 사용이 가능하다.

• 그래프에서 음의 사이클의 존재 여부를 확인할 수 있다.

3. 알고리즘 구현 단계

1. D[K] 배열 생성 : 출발점(S)에서 부터 K 정점까지의 거리를 저장하는 배열

2. 출발점부터 출발점 까지의 최단경로는 무조건 0이니 D[S] = 0으로 초기화한다.

3. D[K]의 나머지 모든 요소를 무한대로 초기화한다.

4. 모든 간선(E)을 확인하는 작업을 총 V-1번 수행한다. (그러므로 시간복잡도는 O(VE)가 된다)

이 때, 어떤 간선 E = (I,J,W)에 대하여 그 가중치가 W라 할 때, 만약 D[I]가 무한대가 아니고 D[J] > D[I] + W이면 D[J]를 D[J] 를 D[I]+W로 갱신한다.

+) V번째 모든 간선을 확인하였을 때 거리배열이 갱신되었다면 그래프 G는 음의 사이클을 가지는 배열이다.

4. 실제 예를 통한 구현

5개의 정점과 8개의 간선으로 이루어진 가중 그래프 G에서 정점 1에서 나머지 정점까지의 최단거리를 구하여라

그래프 사진

그래프 간선

        <그래프 G>      <간선 E>

간선사용횟수	1	2	3	4	5
초기화	0	∞	∞	∞	∞
1번 사용	0	7	5	3	∞
2번 사용	0	6	5	3	-3
3번 사용	0	6	-1	3	-3
4번 사용	0	5	-1	2	-4
5번 사용	0	5	-2	2	-4

<배열 D[K] >

• 위 표를 그리면서 풀려고 하면 2차원 배열로 생성해야할 것 같지만, 사실상 처음 <초기화 행> 부터 5번 반복하면서 같은 배열을 갱신해주면 되기 때문에 1차원 배열인 D[K]만으로도 충분하다.

• 간선 리스트 E를 순회하는 작업을 총 4번 진행하면서, 마지막으로 간선을 4번까지 사용했을 때의 최단경로를 구할 수 있다

• 위와같은 경우 정점이 5개기 때문에 보통의 경우 최단 경로는 최대 4개의 간선까지만 사용한다. 그러므로 5번 이상 반복을 할지라도 더이상 배열이 갱신되지 않아야 맞다.

• 하지만 한번 더 반복을 했는데도 위처럼 배열이 갱신되는 경우가 생길 수 있다. 이런 경우가 바로 위에 설명한 음의 사이클을 가지는 경우이다.

음의 사이클

<음의 사이클>

• 위처럼 그래프가 순환하며 계속해서 음의 가중치를 증가시키는 경우 최단경로를 구하는 것이 불가능하다. 그렇기 때문에 일반적으로 벨만포드 알고리즘을 구현할 때는 V-1번 까지 수행한 뒤 마지막 V번째 반복을 통해 음의 사이클이 있는지 검증을 해야만 한다.

5. 시간복잡도

최단거리를 구하기 위해서 V-1번 E개의 간선을 확인하므로 연산횟수는 (V-1)*E이고 음의 사이클 존재 여부를 확인하기 위해서 한번 더 E개의 간선을 확인하므로 총 연산횟수는 V*E이다. 따라서 시간복잡도는 O(V*E)가 된다.

6. 관련문제 & 코드

백준 11657번 타임머신

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

풀이코드(Java)

http://colorscripter.com/s/R3j2SzC