[Algorithm] 벨만-포드 알고리즘 - 최단 경로 알고리즘 2 🏃‍♀️🏃‍♀️

헛둘 헛둘

벨만-포드 알고리즘(Bellman-Ford Algorithm)은 그래프 탐색의 최단거리 알고리즘 중 하나입니다. 잘 알려진 다익스트라, 플로이드-마샬 알고리즘과 달리 벨만-포드 알고리즘은 음수 가중치를 가진 그래프의 최단 경로를 찾아낼 수 있습니다. 또한 최단 거리 알고리즘에서 치명적인 음수 사이클의 존재도 알아차릴 수 있게 해줍니다. (짱짱 👍👍👍)

이 알고리즘은 저에게 조금 신선하고 재밌는 알고리즘이였습니다. 처음엔 이해도 잘 안 가서 고생했습니다 ㅠㅠ 그래서 제 딴에서는 이해하기 쉽게 알려드리고 싶지만 잘 되려나 모르겠습니다. 벨만-포드 알고리즘의 특징과 구현, 그리고 문제를 풀며 얻은 팁들을 소개해드리려 합니다. 잘 부탁드립니다. 🙏🙏🙏 (gd 스타일 ㅋ)

일단, 이 알고리즘의 특징은 기존의 그래프 탐색 알고리즘과 반대로, 최단거리 탐색시 가중치를 낮은 값부터 쌓아가지 않고, 아주 큰 값 INF에서 점점 깎아냅니다. 기존 BFS에서는 아직 방문하지 않은 노드를 찾은 다음, 현재 노드까지의 가중치 합에다가 다음 노드로의 가중치를 더하는 방식으로 최단거리를 찾아냈습니다.하지만 벨만-포드 알고리즘은 가중치 합에 대한 배열-리스트를 도달 할 수 없는 아주 큰 값으로 초기화 합니다! 그 다음 값을 깎아냅니다. 제 마음대로 깎아낸다고 표현을 했는데, 이는 이해를 돕기 위한 표현입니다. 실제로는 완화, 혹은 이완시킨다고 표현합니다. (영문 위키 백과에서는 relaxtion라고 표현합니다.)

자세히 설명하겠습니다.

노드 B를 제외한, A -> B의 가중치는 w라고 할 때, 노드 B까지의 거리 dist[B]에 대해, 항상 $dist[A] + w >= dist[B]$가 성립합니다. 노드 B까지의 최단거리는 항상 노드 A까지의 거리 + w보다 작거나 같다는 것입니다. 이는 사실 당연하죠? A에서 B로 가는 방법이 가중치가 w인 길 하나인데, A까지의 거리 +w 보다 B까지의 거리가 더 클 수는 없습니다. 이해를 돕기 위해 좀 더 자세히 말 하자면, $dist[A] + w = dist[B]$ 일때가 최단 거리이고, $dist[A] + w > dist[B]$일때는 여기 저기 돌아서 천천히 온 상태가 되겠습니다. 자연스럽게 $dist[A] + w < dist[B]$는 있을 수 없는 일이겠죠? 이 과정을 여러번 반복합니다. 왜 여러번 반복하나요? 우리가 값을 완화시키는 과정에서 찾아낸 A까지의 거리가 '아직' 최단거리가 아닐 수 있습니다. 그러면 B까지의 거리도 최단거리가 아니겠지요? 그러므로 A까지의 거리를 나타낸 값이 '진짜 최단 거리'까지 완화된다면.. B까지의 최단거리 또한 구할 수 있겠죠? 여러번이면 몇 번이여야 할까요? 방금 막 A의 최종 완화를 마쳤다고 가정합시다. A의 최단거리를 찾게 되었습니다. 이때 한번 더 완화를 진행해야 B노드의 최단거리도 알 수 있게 되겠죠? 오, 그러면 노드의 갯수만큼 진행하면 될까요? 아까 초기화 하는 과정에서 모든 노드까지의 거리를 INF라고 가정하기로 했습니다. 이 때 시작 노드 까지의 거리는 0으로 둬야합니다. 그래야 이어진 노드들에 대해 완화가 가능하겠죠? 따라서, 전체 노드의 갯수에서 시작 노드를 빼준 V-1번의 반복이 필요합니다.

V-1번의 완화를 통해 시작점으로 부터 모든 지점의 최단거리를 알게 되는 것이지요. 그렇다면 V번째 완화는 어떻게 될까요? 모든 노드가 가진 거리값이 최단거리이기 때문에 완화가 일어나지 않겠네요! 이미 dist[A] + w = dist[B]이므로, 아무 일도 일어나지 않겠죠? 정말 재밌는 알고리즘이지 않나요? 아주 높은 값을 잡아두고 점점 실제 값에 맞춰 깎아내린다는게 참 신선하고 재밌었습니다.

또한, V번째의 완화는 실패라는 점을 이용해서 음수 사이클을 감지해낼 수 있습니다. 음수 사이클이 있는 그래프는 V번째 완화 시도를 성공해버리기 때문입니다. 왜 그럴까요? V-1번의 완화 과정에서 구해놓은 거리들이 있다고 합시다. 여기에 완화 시도를 해버리면 음수 사이클로 인해 지금까지 구해놓은 거리들 보다 더 낮은 값을 받게 되겠지요? 그덕에 V번째의 완화가 성공해버리게 되는 것입니다.

음수 간선을 계속해서 돌 수 있는 사이클의 존재는 최단 거리 알고리즘에서 치명적입니다. 계속해서 뺑뻉이(?)를 돌면 이제까지 쌓아온 가중치 합이 끝도 없이 낮아지기 때문입니다. 다른 알고리즘을 이용했다면 별 의미가 없는 값들을 돌려받게 되는 것이지요.. 그런 문제를 해결해주는 벨만-포드 알고리즘! 정말 기특허네요 허허

구현은 아래와 같습니다.

전제 노드 개수를 V, 완화 성공 여부를 따지는 불리안을 relaxtion으로 해주었습니다. 그리고 현재까지 완화시킨 결과를 담은 배열을 dist, 노드간 연결을 담은 인접리스트를 vec이라고 해주었습니다. 시작점과 도착점은 start와 dest입니다.

앞서 언급했듯이 시작점의 거리를 0 나머지 노드는 아주 큰 수 INF로 초기화해줬습니다. 그 다음 노드 전체 갯수 V번만큼 완화 시도를 반복하는 for문을 만들어줬습니다. 그리고 매번 완화를 시도 할 때마다 성공 여부를 따지는 relaxtion을 false로 초기화 해줍니다. 그 이유는 다음과 같습니다.

1. 불필요한 반복을 막기 위해서입니다.

한번 완화가 실패했을 경우를 생각해봅시다. 이는 더 이상 완화 할 일이 없다는 뜻인데, 이후의 완화 시도는 어떻게 될까요? 당연히 다음 모든 완화 시도도 전부 실패하게 됩니다. 이를 위해 구현해준 코드가 가장 큰 for문의 마지막 줄입니다. 해당 회차 완화 시도가 실패하면 반복문을 break하도록 해주었습니다.

2. 마지막 시도의 성공 여부를 따지기 위해서입니다.

앞서 언급했던대로 마지막 V번째의 시도가 성공했는지를 따지려면 V번째 시도가 시작 될 때 relaxtion이 false로 초기화 되어있어야 하기 때문입니다.

결국 반복문이 모두 끝났을 때 relaxtion이 true면 음수 사이클이 있는 것이고, false면 없는 것이지요. 이를 구현한것이 함수의 가장 마지막 줄입니다.

마지막으로 반복문 안쪽을 보겠습니다. 모든 노드들을 순회하며 연결된 노드들을 탐색합니다. 다음 노드까지의 가중치합이, 현재 노드까지의 가중치 합 + 두 노드 사이의 가중치 보다 크다면 그 값으로 초기화를 해주고 완화 성공을 알리기 위해 relaxtion을 true로 바꿔줍니다.

이렇게 해서 구현에 대한 설명도 모두 끝났습니다. 다음은 문제를 풀며 얻게된 팁을 소개해주려 합니다.

1. 도달하지 못 하는 노드 탐색

도달하지 못 하는 노드를 탐색할 일이 있습니다. 해당 알고리즘은 자연스럽게 모든 노드를 탐색하게 됩니다. 따라서 출발 지점부터 도착 지점을 포함한 부분 트리 T가 있다고 할 때, T와 전혀 겹치지 않는 다른 부분 트리 T2가 있을 수 있다는 것입니다. 이럴 경우에는 사이클 판단에서도 방해를 받게 될 것입니다. 그럴땐 다음에 이어진 노드의 거리가 INF인지 확인하여 INF면 넘어가는 방법을 이용합니다.

if (dist[next_node] == INF) { continue; }

이런 식의 코드를 추가해줄 수 있겠네요. 애초에 갈 일이 없거나 갈 필요가 없는 곳을 탐색 할 수 있다는 가능성을 배제하고 문제를 풀다보니 정말 많은 고생들을 했었습니다. 🤪🤪

다른 방법도 있습니다. 사이클 여부는 알 필요가 없고 최단거리만 알면 되는 상황에서 쓸 수 있는 방법입니다. (알고리즘 문제해결 전략에서 참고한 방법입니다.) 내가 궁금한 어떤 노드에 탐색이 도달했는지 알고 싶을 때는 어떻게 할까요? 다른 알고리즘과 같이

if (dist[dest] == INF) { return -1; }

이런 식으로 처리해줄까요? 아닙니다! 왜냐하면 T2안의 노드들이 서로 완화를 해줄 수 있기 때문입니다. 그렇게 된다면 가중치 합이 INF보다 조금 작은 어떤 값이 되어버리겠죠? 이럴 때는

if (dist[dest] > INF - 100000000) { return -1; }

이런 식으로 INF에 아주 큰 숫자를 빼준 것보다 큰지를 확인합니다. 이렇게 해결해줄 수 있겠지요?

이제까지 벨만-포드 알고리즘의 팁도 알려드렸습니다.

벨만-포드 알고리즘은 음수 간선이 있을 때 이용 할 수 있는 아주 유용한 알고리즘이였습니다. 별거 아닌거 같지만 음수 간선이나 음수 사이클의 존재 여부는 최단 경로를 알고자 할때 치명적인 걸림돌일 수 있기 때문입니다. 다른 최단 경로 알고리즘도 공부해보세요! 아래 링크 첨부하겠습니다. 읽어주셔서 감사합니다. 불꽃카리스마진호우!^^였습니다.

(해당 글은 알고리즘 문제해결 전략이라는 책을 참고하여 작성했습니다.)

다익스트라 알고리즘 - 최단 경로 알고리즘 1 🏃🏃 - 이진호.불로그.이름추천. 받수다. (tistory.com)

플로이드-와샬 알고리즘 - 최단 경로 알고리즘 3 🏇🏇 - 이진호.불로그.이름추천. 받수다. (tistory.com)