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

벨만 포드 알고리즘

벨만-포드 알고리즘은 다익스트라 알고리즘과 마찬가지로 한 정점을 기준으로 다른 모든 정점까지의 최단경로를 구하여 결과적으로 원하는 도착지까지의 최단경로를 도출해 내는 알고리즘이다. 하지만 다익스트라 알고리즘과 다르게 그래프에 음의 가중치가 있어도 최단 경로를 구할 수 있다.

[알고리즘] 다익스트라(Dijkstra)

 

다익스트라와 음의 가중치

다익스트라 알고리즘 과정

1. 시작정점 선택
2. 거리 배열 초기화 (시작정점은 0으로 다른 노드는 무한대로)
3. 지금까지 방문하지 않은 정점 중 가장 짧은 거리를 가진 정점 방문
4. 현재 방문한 정점과 인접한 정점들의 거리 값을 갱신
5. 단계 3과 4를 반복

 

다익스트라 알고리즘은 벨만-포드와 다르게 그리디한 동작방식을 가지고 있다. 다익스트라 알고리즘의 과정을 살펴보면 그래프를 탐색하는 과정에서 “방문하지 않은 정점 중 가장 짧은 거리를 가진 정점을 선택”하여 다른 정점까지의 최단거리를 구해나간다. 이때 가장 짧은 거리를 가진 정점을 선택하는 과정이 바로 그리디한 동작 방식이다.

그리디한 방식은 현재 시점에서 가장 짧은 거리를 가진 정점만을 선택하여 다음 차례로 방문하는데, 선택한 가장 짧은 거리를 이용하여 나머지 정점까지의 거리를 계산하기 때문이다. 이 개념은 다시 생각해 보면 현재 시점에서 가장 짧지 않은 다른 정점은 방문할 필요도 없기 때문에 탐색하지 않게 된다.

아래의 그래프를 참조해 정점 1에서 정점 2까지의 최단 경로를 구해보자. 정점 1을 방문하여 정점 2, 3의 거리배열을 각 5와 10으로 갱신했다. 그다음 방문할 정점을 택할 때 그리디하게 거리가 가장 짧은 정점 2를 택한다. 계산 없이 눈으로 그래프를 보더라도 정점 1에서 정점 2까지 가는데 굳이 거리가 10이나 되는 정점 3을 거쳐갈 필요가 전혀 없다. 따라서 정점 3의 거리는 배열의 값을 업데이트하는 데에 쓰이지 않으므로 방문하지 않고 그대로 최단거리 배열이 확정된다.

너무나 당연한 과정을 길게 설명했는데, 그래프의 가중치를 하나만 바꾸어보자. 아래의 그래프 같은 경우는 정점 3을 거쳐가는 경로가 음수의 가중치를 만나게 되어 최단경로가 된다. 즉, 음의 가중치가 그래프에 존재할 때에는 그리디한 다익스트라 알고리즘으로는 최단 경로를 도출해낼 수 없다. 이 때 이용할 수 있는 알고리즘이 벨만-포드 알고리즘이고 다익스트라와 다르게 그리디한 동작 방식을 버리고 모든 정점을 방문해 보는 방식으로 최단 경로를 도출한다.

음의 가중치가 존재하는 그래프

하지만 벨만-포드 알고리즘 또한 최단 경로를 구할 수 없는 경우가 있는데, 그래프에 음의 사이클이 존재할 경우 최단 경로를 도출할 수 없다.

 

음의 사이클

음의 사이클이란 그래프에 존재하는 사이클 중 가중치의 합이 음수가 되는 사이클을 말한다. 음의 사이클이 그래프에 존재하는 경우 해당 사이클을 지나치는 경우 가중치의 합(거리의 합)이 줄어들게 되고, 사이클을 순환할수록 가중치가 줄어들게 되어 실질적인 최단 경로를 구하기 힘들다. (사이클의 순환을 무한히 반복 → 거리가 무한하게 줄어듦) 따라서 벨만-포드 알고리즘에선 음의 사이클이 발견될 경우 최단 경로가 존재하지 않는다고 판단한다.

음의 사이클 존재 →  최단 경로 구할 수 없음

사이클은 존재하나 음의 사이클 아님 (가중치의 합이 양수) → 최단 경로 구할 수 있음

---

벨만-포드 알고리즘 과정

1. 시작정점 선택
2. 거리 배열 초기화 (시작정점은 0으로 다른 노드는 무한대로)
3. 모든 간선을 따라 모든 정점을 방문하며 최단 거리 값 갱신
4. 3번 과정을 (정점 수 - 1) 번 반복
5. 3번 과정을 1번 더 반복하여 최단 거리가 갱신되는 지 확인 (음수 사이클 검출 과정)

시작 정점: 1

거리 배열 초기화

https://engkimbs.tistory.com/363

 

모든 정점을 방문하며 최단 거리 값 갱신

모든 간선을 따라 모든 정점을 방문하여 각 정점까지의 최단 거리를 계산하여 업데이트해 준다. 업데이트 조건은 다익스트라와 마찬가지로 현재 노드를 거처 가는 경우의 가중치가 더욱 작으면 거리를 갱신해 준다.
dis[인접정점] = min(dis[인접정점], dis[현재정점] + cost(현재정점🠒인접정점))

예를 들어 위의 그림에서 현재 방문한 정점이 2인 경우에 연결되어 있는 정점은 4번 정점이고 원래 배열에 있던 거리 2보다 정점 2를 거쳐 가는 거리 -5가 더욱 작기 때문에 업데이트해준다.
dis[4] = min(dis[4], dis[2] + cost(2 → 4)) = min( 2, (-4)+(-1)) = -5

 

위의 과정을 (정점 수 - 1) 번 반복

이 예시에서는 업데이트가 1회만에 끝나버렸...

다익스트라는 특정 정점을 한 번 방문하면 출발노드에서 해당 정점까지의 최단 거리가 확정된다. 하지만 벨만-포드 알고리즘은 최단거리의 근사치를 점진적으로 개선하는 것이기 때문에, 모든 정점을 한번씩 방문하였어도 최단거리가 확정되지 않을 수 있다. 위의 과정(모든 노드를 다 방문하여 거리 계산)을 한번 할 때마다 최소 하나의 정점에 대한 최단 거리는 정해진다. 따라서 (정점 수 -1) 번 반복해야 최단 거리를 보장할 수 있다.

최단 거리의 간선 수는 항상 그래프 (정점 수-1) 보다 작거나 같다. 그 이상의 간선을 지나게 되면 중복되는 정점을 지나치게 되어 최단거리가 될 수 없다. 따라서 위의 과정을 (정점 수 -1)번 반복하여 모든 정점까지의 최단거리를 보장할 수 있다.

 

음수 사이클 체크

위에서 설명했듯 벨만-포드 알고리즘은 음수 사이클이 그래프 내에 존재하면 최단 거리를 구할 수 없다. 따라서 음수 사이클이 존재하는지 체크하는 과정이 필요하다. 방법은 간단하게 위에서 했던 업데이트 과정을 한 세트 더 해주는 것이다. 이미 각 정점까지의 최단 거리를 보장하기 위해 (정점 수 - 1)번 업데이트 과정을 반복했다. 여기서 업데이트 과정을 더 진행해도 업데이트가 되지 않아야 정상이다. (예시로 든 그래프에서는 한 번만 해도 업데이트가 진행되지 않았음...)

반대로 이때 업데이트가 또 진행된다면 어디선가 음수 사이클이 존재하여 순회할 때마다 가중치의 합이 줄어들고 있다는 것을 나타내기 때문에 최단거리를 구할 수 없음을 뜻한다.