최단 경로(Shortest Path)는 그래프의 종류에 따라 그 진의가 다르게 해석될 수도 있는 주제입니다. 가중치가 없는 그래프에서는 간선 개수가 가장 적은 경로가 최단 경로이지만 가중치가 있는 그래프에서는 일반적으로 시작 노드에서 끝 노드까지 이동할 때 거치는 간선의 가중치의 총합이 최소가 되는 것을 말합니다. 이를테면 다음 그래프는 간선에 가중치가 있으므로 최단 경로의 기준은 간선의 가중치의 총합입니다.
노드 1에서 5까지의 최단 경로를 구한다고 했을 때, 간선 개수를 기준으로 하면 1 → 5는 간선의 개수가 1개로 가장 적으니 이것이 최단 경로가 됩니다. 하지만 가중치의 합을 기준으로 하면 1 → 5는 가중치가 49이고, 1 → 2 → 5는 가중치가 24이므로 이것이 최단 경로가 됩니다. 여기서는 최단 경로를 구하는 대표적인 알고리즘인 다익스트라 알고리즘, 벨만-포드 알고리즘을 차례로 알아보겠습니다.
2편은 벨만-포드 알고리즘입니다.
벨만-포드 알고리즘
벨만-포드(Bellman-ford) 알고리즘 역시 다익스트라 알고리즘과 마찬가지로 노드에서 노드까지의 최소 비용을 구한다는 점에서는 같습니다. 하지만 벨만-포드 알고리즘은 매 단계마다 모든 간선의 가중치를 다시 확인하여 최소 비용을 갱신하므로 음의 가중치를 가지는 그래프에서도 최단 경로를 구할 수 있습니다. 벨만-포드 알고리즘은 다음과 같이 동작합니다.
- 시작 노드를 설정한 다음 시작 노드의 최소 비용은 0, 나머지 노드는 INF로 초기화합니다. 이후 최소 비용을 갱신할 때 직전 노드도 갱신합니다.
- 노드 개수 – 1만큼 다음 연산을 반복합니다.
2-1 시작 노드에서 갈 수 있는 각 노드에 대하여 전체 노드 각각을 거쳐갈 때 현재까지 구한 최소 비용보다 더 적은 최소 비용이 있는지 확인하여 갱신합니다. 최소 비용을 갱신할 때, V의 직전 노드 값도 같이 갱신합니다.
- 과정 2를 마지막으로 한 번 더 수행하여 갱신되는 최소 비용이 있는지 확인합니다. 만약 있다면 음의 순환이 있음을 의미합니다.
벨만-포드 알고리즘은 글로만 읽으면 쉽게 와닿지 않습니다. 아마도 ‘노드 개수 – 1만큼 연산을 반복하라’는 말과 과정 3의 ‘한 번 더 수행하라’는 말이 쉽게 와닿지 않을 겁니다. 우선은 벨만-포드 알고리즘이 동작하는 과정을 자세히 살펴보고 그 이후에 왜 그렇게 하는지에 대해 설명해보겠습니다.
01단계 우선 시작 노드를 A로 정하고 최소 비용을 0, 직전 노드를 A, 나머지 노드는 INF로 초기화했습니다.
02단계 노드 A에서 A를 거쳐 각 노드 B, C, D, E까지 가는 비용 중 현재까지 구한 최소 비용보다 적은 값이 있는지 확인하고 현재까지 구한 최소 비용보다 비용이 적다면 갱신합니다. 이때 여러분이 비교와 갱신 과정을 보기 편하도록 해당 정점의 최소 비용은 최소_비용(A)(숫자), 가중치가 있는 간선은 간선(A, B)(숫자)와 같이 표시하겠습니다. 또한 간선이 없는 경우는 INF로 계산한다는 점에도 주의합니다.
※ A에서 A를 거친다라고 표현한 이유는 A가 시작 노드이기 때문입니다. A에서 시작하면 A를 거치는 것으로 생각해도 됩니다.
- 최소_비용(A)(0) == 최소_비용(A)(0) + 간선(A, A)(0) : 갱신하지 않음
- 최소_비용(B)(INF) > 최소_비용(A)(0) + 간선(A, B)(4) : 최소_비용(B)를 INF에서 4로 갱신
- 최소_비용(C)(INF) > 최소_비용(A)(0) + 간선(A, C)(3) : 최소_비용(C)를 INF에서 3으로 갱신
- 최소_비용(D)(INF) == 최소_비용(A)(0) + 간선(A, D)(INF) : 갱신하지 않음
- 최소_비용(E)(INF) > 최소_비용(A)(0) + 간선(A, E)(-6) : 최소_비용(E)를 -6으로 갱신
03단계 다음도 해봅시다. 노드 A에서 B를 거쳐 각 노드까지 가는 최소 비용도 갱신해봅니다.
- 최소_비용(A)(0) < 최소_비용(B)(4) + 간선(B, A)(INF) : 갱신하지 않음
- 최소_비용(B)(4) == 최소_비용(B)(4) + 간선(B, B)(0) : 갱신하지 않음
- 최소_비용(C)(3) < 최소_비용(B)(4) + 간선(B, C)(INF) : 갱신하지 않음
- 최소_비용(D)(INF) > 최소_비용(B)(4) + 간선(B, D)(5) : 9로 갱신
- 최소_비용(E)(-6) < 최소_비용(B)(4) + 간선(B, E)(-6) : 갱신하지 않음
04단계 이제 슬슬 갱신하는 패턴이 눈에 익을 것입니다. 노드 A에서 C를 거쳐 각 노드까지 가는 최소 비용도 갱신합시다. 예를 들어 노드 C를 거쳐서 B로 가는 새 경로는 기존의 B의 최소 비용보다 크므로 갱신하지 않습니다.
- 최소_비용(A)(0) < 최소_비용(C)(3) + 간선(C, A)(INF) : 갱신하지 않음
- 최소_비용(B)(4) < 최소_비용(C)(3) + 간선(C, B)(2) : 갱신하지 않음
- 최소_비용(C)(3) == 최소_비용(C)(3) + 간선(C, C)(0) : 갱신하지 않음
- 최소_비용(D)(9) < 최소_비용(C)(3) + 간선(C, D)(INF) : 갱신하지 않음
- 최소_비용(E)(-6) < 최소_비용(C)(3) + 간선(C, E)(INF) : 갱신하지 않음
05단계 노드 A에서 D를 거쳐가는 방법은 없으므로 갱신하지 않습니다.
06단계 노드 A에서 E를 거쳐 각 노드까지 가는 최소 비용도 갱신합니다. 모든 최단 경로에 대해 노드의 최소 비용을 체크했으므로, 벨만-포드 알고리즘의 첫 번째 반복이 끝났습니다.
- 최소_비용(A)(0) < 최소_비용(E)(-6) + 간선(E, A)(INF) : 갱신하지 않음
- 최소_비용(B)(4) < 최소_비용(E)(-6) + 간선(E, B)(2) : 갱신하지 않음
- 최소_비용(C)(3) == 최소_비용(E)(-6) + 간선(E, C)(0) : -4로 갱신
- 최소_비용(D)(9) < 최소_비용(E)(-6) + 간선(E, D)(INF) : 갱신하지 않음
- 최소_비용(E)(-6) < 최소_비용(E)(-6) + 간선(E, E)(INF) : 갱신하지 않음
07단계 이제 첫 번째 반복이 끝났습니다. 위에서 했던 과정을 ‘노드 개수 – 1’번 반복한다고 했으므로 01단계 01단계~06단계 06단계를 4번 더 반복하면 됩니다.
08단계 하나만 해봅시다. 노드 A에서 A를 거쳐 각 노드까지 가는 비용을 갱신합니다. 첫 번째 과정과 마찬가지 과정을 반복하면 됩니다. 앞 과정에서 최소 비용을 갱신했으므로 또 다른 갱신이 진행될 것입니다.
- 최소_비용(A)(0) == 최소_비용(A)(0) + 간선(A, A)(0) : 갱신하지 않음
- 최소_비용(B)(4) == 최소_비용(A)(0) + 간선(A, B)(4) : 최소_비용(B)를 INF에서 4로 갱신
- 최소_비용(C)(-4) < 최소_비용(A)(0) + 간선(A, C)(3) : 갱신하지 않음
- 최소_비용(D)(9) > 최소_비용(A)(0) + 간선(A, D)(INF) : 갱신하지 않음
- 최소_비용(E)(-6) == 최소_비용(A)(0) + 간선(A, E)(-6) : 최소_비용(E)를 -6으로 갱신
이제 벨만-포드 알고리즘이 어떤 식으로 최단 거리를 알아내는지 알았을 겁니다. 그럼 앞서 말끔하게 풀지 못했던 다음 두 가지 궁금증을 해결하며 벨만-포드 알고리즘 설명을 마치겠습니다.
왜 정점 개수 -1만큼 반복하는가? 매 연산마다 최단 경로가 1개씩 확정되므로!
아래와 같은 그래프에서 시작 노드가 1일 때 최단 경로를 구하는 상황을 생각해봅시다. 벨만-포드 알고리즘이 연산을 K번 반복하면 K개의 간선에 대한 최단 경로를 구할 수 있습니다. 예를 들어 첫 번째 반복 과정에서는 노드 2에 대한 최단 경로가, 두 번째 반복 과정에서는 노드 3에 대한 최단 경로가 결정됩니다. 이런 식으로 N – 1번 연산을 반복하면 노드 N에 대한 최단 경로가 결정되어 벨만-포드 알고리즘이 끝나는 것이지요. 그래서 노드 개수 – 1만큼 벨만-포드 알고리즘의 연산을 반복했던 것입니다.
왜 한 번 더 연산을 반복하는가? 음의 순환을 찾기 위해!
그런데 위 그림에서 노드 N의 최단 경로를 구성하는 간선 개수가 N개 이상이면 최단 경로의 간선 개수는 최대 N – 1이어야 하므로 뭔가 잘못된 것을 의미합니다. 즉, 음의 순환이 있는 것입니다. 지금 여러분이 보고 있는 그래프에 노드 N에서 노드 N – 1으로 향하는 가중치가 -100인 간선을 추가했다고 생각해봅시다.
그러면 음의 순환인 N → (N – 1) 구간을 반복하면 계속해서 최소 비용(가중치의 합; -100)은 점점 줄어듭니다. 그렇다는 건 최단 경로를 구할 수 없다는 거네요. 이 음의 순환을 계속해서 돌면 최소 비용은 무한히 작아질 테니까요.
음의 순환에 빠지는 건 벨만-포드 알고리즘의 한계다?
흔히 벨만-포드의 알고리즘의 한계점으로 ‘음의 순환이 있을 때 최단 경로를 구하지 못한다’를 자주 말합니다. 이 말을 듣고 ‘벨만-포드 알고리즘은 음의 순환이 있을 때 최단 경로를 구하지 못하는 좋지 못한 녀석’이라고 오해하기 쉬운데 그렇게만 이해하면 안 됩니다.
사실 엄밀히 말하면 그래프에 음의 순환이 있으면 어떤 알고리즘도 최단 경로를 구할 수 없습니다. 다만 음의 가중치를 다루는 최단 경로 알고리즘은 음의 순환에 빠질 수 있는 것이죠. 다시 말해 벨만-포드 알고리즘은 음의 가중치가 있는 그래프에서 최단 경로를 찾을 수 있는 대신 음의 순환에 빠질 수 있고, 다익스트라 알고리즘은 음의 가중치가 있는 그래프에서 동작하지 못하므로 아예 언급되지 않는 것입니다.
그러니 음의 순환에 빠지는 벨만-포드 알고리즘의 특징을 알고리즘의 한계로 보면 안 됩니다. 오히려 음의 순환을 감지할 수 있는 것이죠.
💡합격 조언: 플로이드-워셜 알고리즘
플로이드-워셜(floyd-warshall) 알고리즘은 노드에 대하여 각 노드부터 나머지 노드까지의 최단 경로를 모두 구하는 알고리즘입니다. 출제 빈도가 낮아 소개하지 않았습니다.
지금까지 다익스트라 알고리즘, 벨만-포드 알고리즘을 알아봤습니다. 각 알고리즘의 목적은 최단 경로, 최소 비용을 찾는다는 점에서 같습니다. 하지만 세세하게 들여다보면 장단점과 구체적인 목표가 달랐습니다. 표로 정리하며 마무리하겠습니다.
자료구조, 알고리즘, 빈출 100 문제로 대비하는 코테 풀 패키지
[되기] 코딩 테스트 합격자 되기(파이썬 편)
저자 박경록
매일 퇴근과 점심 메뉴를 고민하는 9년차 시스템 S/W 개발자입니다. 수학, 알고리즘 같은 실생활과 가깝고도 먼 학문을 좋아하고, 명확하지만 개선 여지가 있는 문제들에 대해 논의하고 사고를 개선해 나가는 과정을 좋아합니다.
