가장 빠르고 효율적인 최단 거리 탐색 기법으로 칭송받는 다익스트라(Dijkstra) 알고리즘에게는 절대 마주쳐서는 안 될 치명적인 약점이 하나 있습니다. 바로 '음수 가중치(Negative Weight)'를 가진 간선의 존재입니다. 도로망을 안내하는 내비게이션이라면 거리가 마이너스(-)가 될 리 없겠지만, 금융 시장의 환율 차익 거래(Arbitrage)를 분석하거나, 연료를 소모하는 대신 충전소가 있어 에너지를 환급받는 드론 경로를 계산할 때는 "비용이 줄어드는" 음수 가중치가 반드시 필요합니다. 다익스트라가 포기한 이 음수 가중치의 늪을 완벽하게 건너고, 나아가 시스템을 붕괴시키는 '음수 사이클'까지 감지해 내는 구원자, 벨만-포드(Bellman-Ford) 알고리즘의 동작 원리를 깊이 있게 해부해 봅니다.
1. 벨만-포드 알고리즘의 탄생: 다익스트라의 한계 극복
다익스트라 알고리즘은 "한 번 방문 처리가 끝나서 최단 거리가 확정된 노드는, 이후에 어떤 길을 돌아오더라도 거리가 더 짧아질 수 없다"는 확고한 믿음(그리디)을 바탕으로 속도를 냅니다. 하지만 중간에 `-50`이라는 음수 간선이 끼어있다면 어떨까요? 이미 최단 거리라고 확정 지어버린 노드에 나중에 뒤통수를 치며 더 짧은 경로가 등장하게 됩니다. 다익스트라는 뒤를 돌아보지 않는 성격 탓에 이 갱신을 무시해 버리고 오답을 냅니다.
이 문제를 해결하기 위해 고안된 벨만-포드 알고리즘은 그리디(Greedy) 방식을 과감히 버리고, 무식하지만 꼼꼼한 전수 조사 방식(Dynamic Programming)을 택했습니다. "확정 짓지 말고, 매번 전체를 다 뒤져서 갱신될 여지가 있는지 확인하자"는 것이 핵심 철학입니다.
2. 벨만-포드의 동작 원리: 정점 개수 $V-1$번의 반복
벨만-포드 알고리즘의 동작은 다익스트라보다 오히려 직관적이고 단순합니다. 시작 노드의 거리를 0으로 초기화하고, 나머지 노드를 무한대($\infty$)로 둔 상태에서 다음의 핵심 로직을 수행합니다.
2-1. 왜 하필 $V-1$번 반복할까? (Relaxation)
그래프에 존재하는 정점의 총개수가 $V$개일 때, 알고리즘은 그래프 내에 있는 '모든 간선(Edge)'을 하나씩 확인하며 최단 거리 테이블을 갱신하는 과정을 정확히 $V-1$번 반복합니다.
어떤 정점에서 다른 정점으로 가는 최단 경로는, 아무리 빙빙 돌아간다고 해도 최대 $V-1$개의 간선을 지날 수밖에 없습니다. (만약 $V$개 이상의 간선을 지난다면, 그것은 이미 방문했던 노드를 또 방문하여 순환(Cycle)이 생겼다는 뜻이기 때문입니다.) 따라서 모든 간선을 한 번씩 확인하여 갱신(Relaxation)하는 이 과정을 $V-1$번 반복하면, 아무리 멀리 떨어진 노드라도 완벽하게 최단 거리가 찾아짐이 수학적으로 증명되어 있습니다.
3. 최강의 무기: '음수 사이클(Negative Cycle)' 감지 기능
벨만-포드가 단순히 음수 간선을 계산할 수 있다는 것을 넘어 위대한 알고리즘으로 평가받는 이유는 바로 음수 사이클 판별 기능 때문입니다.
3-1. 타임머신과 같은 늪, 음수 사이클
만약 A $\rightarrow$ B $\rightarrow$ C $\rightarrow$ A로 빙글빙글 도는 순환 경로가 있는데, 이 경로를 한 바퀴 돌 때마다 비용이 총합 `-10`이 된다고 가정해 보십시오. 이 궤도에 진입한 프로그램은 거리를 줄이기 위해 무한히 뺑뺑이를 돌며 최단 거리를 마이너스 무한대($-\infty$)로 추락시킬 것입니다. 이를 '음수 사이클'이라고 부릅니다.
3-2. V번째 반복의 비밀
벨만-포드는 이 음수 사이클의 존재 여부를 아주 명쾌하게 잡아냅니다. 앞서 말씀드린 $V-1$번의 전체 간선 확인 반복이 모두 끝난 직후, 단 한 번(즉, $V$번째) 더 전체 간선을 확인해 봅니다. 이론상 $V-1$번 반복으로 모든 최단 거리가 고정(확정)되어야 정상인데, $V$번째 확인에서조차 거리가 또다시 더 짧은 값으로 갱신(Update)되는 노드가 발생한다면? 그것은 바로 음수 사이클이 존재하여 값이 무한히 작아지고 있다는 명백한 증거가 됩니다. 알고리즘은 이 순간 오류(False)를 반환하며 사이클의 존재를 알립니다.
4. 시간 복잡도와 성능 비교 (Trade-off)
벨만-포드는 다익스트라보다 느립니다. 간선의 개수를 $E$라고 할 때, 매 반복마다 모든 간선을 다 확인하므로 시간 복잡도는 $O(VE)$가 됩니다. 다익스트라의 $O(E \log V)$에 비하면 훨씬 무겁고 느립니다. 따라서 코딩 테스트나 실무 아키텍처를 설계할 때, 음수 간선이 단 하나도 없다면 무조건 다익스트라를 사용하고, 음수 간선이 존재하거나 환율 차익 거래처럼 사이클 검출이 필수적일 때만 조커 카드처럼 벨만-포드를 꺼내 드는 것이 엔지니어의 올바른 자세입니다.
1. 벨만-포드(Bellman-Ford) 알고리즘은 다익스트라가 처리하지 못하는 음수 가중치(-) 간선이 포함된 그래프에서도 단일 출발지 최단 경로를 구해냅니다.
2. 모든 간선의 비용을 갱신하는 과정을 총 $V-1$번 무식하게 반복(DP 방식)하므로 시간 복잡도는 다소 느린 $O(VE)$를 가집니다.
3. 정해진 루프를 넘어선 $V$번째 반복에서도 거리 값이 갱신된다면, 시스템을 무한 루프에 빠뜨리는 '음수 사이클(Negative Cycle)'이 존재함을 완벽하게 감지해 낼 수 있습니다.