벨만 포드 알고리즘이란?
한 노드에서 다른 노드까지 최단 거리를 구하는 데 사용하는 알고리즘입니다.
벨만 포드 알고리즘은 다익스트라 알고리즘에 비해 시간이 오래 걸린다는 단점이 있지만 음수의 가중치에도 사용할 수 있다는 장점이 있습니다.
따라서 양수의 가중치로 구성된 그래프에서 최단 거리를 구할 때는 다익스트라 알고리즘을, 음수의 가중치가 포함된 그래프에서는 벨만 포드 알고리즘을 사용합니다.
그래서 어떻게 사용해?
위의 그래프로 벨만 포드 알고리즘을 사용해보겠습니다.
먼저 시작점을 A로 잡고 거리를 초기화해주겠습니다.
| dis[A] | dis[B] | dis[C] | dis[D] | dis[E] | dis[F] |
|---|---|---|---|---|---|
| 0 | INF | INF | INF | INF | INF |
자 이제 탐색을 해볼까요~?
시작점 A에서부터 각 간선들을 탐색하며 거리가 작은 값으로 업데이트해 주겠습니다.
| dis[A] | dis[B] | dis[C] | dis[D] | dis[E] | dis[F] |
|---|---|---|---|---|---|
| 0 | -1 | INF | INF | INF | 7 |
정점 B와 연결된 간선에 대해 업데이트해 주겠습니다
| dis[A] | dis[B] | dis[C] | dis[D] | dis[E] | dis[F] |
|---|---|---|---|---|---|
| 0 | -1 | 7 | INF | 1 | 7 |
나머지 정점 C, D, E, F에 대해 업데이트해 주겠습니다.
| dis[A] | dis[B] | dis[C] | dis[D] | dis[E] | dis[F] |
|---|---|---|---|---|---|
| 0 | -1 | 7 | 2 | 1 | 7 |
| dis[A] | dis[B] | dis[C] | dis[D] | dis[E] | dis[F] |
|---|---|---|---|---|---|
| 0 | -1 | 7 | 2 | 1 | 3 |
정점 E는 간선이 없으니 패스~
| dis[A] | dis[B] | dis[C] | dis[D] | dis[E] | dis[F] |
|---|---|---|---|---|---|
| 0 | -7 | 5 | 2 | 1 | 3 |
자 이렇게 그래프 탐색을 완료했습니다.
근데 지금까지 탐색하면서 뭔가 이상한 점 못 찾으셨나요?
네 맞습니다. 탐색을 여러 번 하면 할수록 C, D, F, 그리고 사이클에 연결된 E의 값은 점점 줄어들어 음의 무한대로 향할 것입니다.
이럴 때는 최단 거리를 구할 수가 없겠죠.
자 그러면 어떻게 음의 사이클이 존재하는지 알 수 있을까요?
간단합니다. 위의 과정을 한 번 더 반복해서 값이 변경되는지 안 하는지 확인하면 되는 것이죠
음의 사이클이 존재한다면, 값이 변경될 테니깐요.
어제보다 더 나은 오늘이 되자