벨만-포드 알고리즘
어떤 최단 경로 문제에는 경로를 더 싸게 만드는 간선이 있습니다. 환불, 내리막길, 유리한 환율 같은 것이죠. 다익스트라 알고리즘은 이런 간선을 감당하지 못합니다. 벨만-포드 알고리즘은 영리함 대신 끈기로 이를 해냅니다.
아이디어
모든 최단 경로 알고리즘은 간선 완화라는 한 가지 동작에 기댑니다. u까지 간 다음 간선 u → v를 따라가는 것이 v까지 알려진 가장 좋은 길보다 짧으면 그 길을 씁니다. 다익스트라 알고리즘은 각 간선을 한 번씩, 음수 간선이 없을 때만 통하는 영리한 순서로 완화합니다. 벨만-포드는 그런 가정을 하지 않습니다. 거리가 더 이상 바뀌지 않을 때까지 어떤 고정된 순서로든 모든 간선을 거듭 완화합니다.
단계별 설명
시작 노드에 거리 0을, 다른 모든 노드에 무한대를 줍니다. 노드가 n개이면 n − 1번 반복합니다. 모든 간선 u → v를 살펴 u에 거리가 있으면 완화합니다. 패스 한 번 동안 아무것도 바뀌지 않으면 일찍 멈춥니다. 그다음 패스를 한 번 더 합니다. 여전히 완화할 수 있는 간선이 있으면 시작 노드에서 총합이 음수인 사이클에 도달할 수 있는 것이고, 그렇지 않으면 모든 거리가 최단이며 기억해 둔 노드가 경로를 알려 줍니다.
예제
단방향 간선 A → B 길이 4, A → C 5, B → D 2, C → B −3을 이 순서로 A에서부터 확인합니다. 패스 1에서 B는 4, C는 5, D는 6을 얻고, 이어서 C → B가 B를 5 − 3 = 2로 낮춥니다. 패스 2에서 D가 2 + 2 = 4로 낮아집니다. 패스 3에서는 아무것도 바뀌지 않으므로 답은 B 2, C 5, D 4입니다. 다익스트라 알고리즘이었다면 음수 간선을 보기 전에 B를 4로, D를 6으로 확정했을 것입니다. 길이 −4인 간선 D → C를 더하면 사이클 C → B → D → C의 총합은 −5가 됩니다. 패스마다 거리가 다시 낮아지고, 확인용 패스가 이를 알려 줍니다.
n − 1번의 패스로 충분한 이유
최단 경로가 있다면 같은 노드를 되풀이해 지나지 않으므로 간선이 n − 1개 이하입니다. 한 패스에서 모든 간선을 완화하면, 간선 순서가 어떻든 올바르게 알려진 최단 경로가 모두 간선 하나만큼 늘어납니다. 그래서 패스 k 뒤에는 간선이 k개 이하인 최단 경로가 모두 옳고, n − 1번의 패스 뒤에는 전부 옳습니다. 그래도 순서는 속도에 영향을 줍니다. 좋은 순서라면 한두 번의 패스로 끝날 수 있습니다.
역사와 활용
알폰소 심벨(Alfonso Shimbel)이 1955년에, 레스터 포드 주니어(Lester Ford Jr.)가 1956년에, 에드워드 F. 무어(Edward F. Moore)가 1957년에, 리처드 벨만(Richard Bellman)이 1958년에 이 방법을 설명했습니다. 이름은 그중 벨만과 포드에서 따왔습니다. 패스는 라우터마다 혼자서 실행할 수 있어서, RIP 같은 거리 벡터 라우팅 프로토콜의 바탕이 되었습니다. 금융에서는 환율에 음의 로그를 취하면 이익이 나는 한 바퀴의 통화 거래(차익 거래)가 음수 사이클이 되며, 벨만-포드로 이를 찾을 수 있습니다.
직접 해 보기
앱을 열고 단계를 누르세요. 모든 간선은 단방향이고, 일부 길이는 음수입니다. 단계마다 고정된 순서로 간선 하나를 확인하며, 타일에는 현재 패스와 그 패스에서 바뀐 거리의 수가 나옵니다. 대개 곧 아무것도 바뀌지 않는 패스가 나와 탐색이 일찍 멈춥니다. 음수 사이클 추가를 체크하고, 확인용 패스가 사이클을 찾아 빨간색으로 그릴 때까지 패스마다 거리가 계속 줄어드는 모습을 지켜보세요.
자주 묻는 질문
벨만-포드 알고리즘의 시간 복잡도는?
노드 V개, 간선 E개에 대해 O(V · E)입니다. 패스는 많아야 V − 1번이고, 패스마다 모든 간선을 확인합니다. 일찍 멈추는 기법 덕분에 실제로는 훨씬 빠른 경우가 많고, 가장 좋은 경우에는 패스 한 번으로 충분합니다.
음수 사이클이란 무엇인가요?
간선 길이의 합이 0보다 작은 사이클입니다. 계속 돌면 경로를 원하는 만큼 짧게 만들 수 있으므로, 그 사이클을 거쳐 도달할 수 있는 모든 노드까지의 최단 거리는 정의되지 않습니다.
벨만-포드 알고리즘은 무방향 그래프에서도 작동하나요?
음수 간선이 없을 때만 그렇습니다. 무방향 음수 간선은 왔다 갔다 할 수 있으므로, 그 자체가 간선 두 개로 된 음수 사이클입니다. 음수가 아닌 간선이라면 작동하지만 다익스트라 알고리즘이 더 빠릅니다.
SPFA란 무엇인가요?
Shortest Path Faster Algorithm의 약자로, 큐를 써서 거리가 방금 바뀐 노드에서 나가는 간선만 다시 확인하는 벨만-포드의 변형입니다. 대개 훨씬 빠르지만 최악의 경우는 같습니다.
시도해 볼 준비가 되셨나요?
브라우저에서 PictorX를 엽니다. 설치가 필요 없고 시작하는 데 신용 카드가 필요하지 않습니다.
벨만-포드 알고리즘 해 보기