벨만-포드 알고리즘

어떤 최단 경로 문제에는 경로를 더 싸게 만드는 간선이 있습니다. 환불, 내리막길, 유리한 환율 같은 것이죠. 다익스트라 알고리즘은 이런 간선을 감당하지 못합니다. 벨만-포드 알고리즘은 영리함 대신 끈기로 이를 해냅니다.

단방향 화살표가 있고 일부 간선이 음수인 그래프. 노드에는 지금까지 찾은 거리가 적혀 있고, 음수 사이클이 빨간색으로 그려져 있다
단방향 화살표가 있고 일부 간선이 음수인 그래프. 노드에는 지금까지 찾은 거리가 적혀 있고, 음수 사이클이 빨간색으로 그려져 있다

아이디어

모든 최단 경로 알고리즘은 간선 완화라는 한 가지 동작에 기댑니다. 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 같은 거리 벡터 라우팅 프로토콜의 바탕이 되었습니다. 금융에서는 환율에 음의 로그를 취하면 이익이 나는 한 바퀴의 통화 거래(차익 거래)가 음수 사이클이 되며, 벨만-포드로 이를 찾을 수 있습니다.

1962년의 리처드 벨먼, 알프레드 아이젠스타트 촬영. 그는 심벨, 포드, 무어에 이어 1958년에 이 최단 경로 방법을 발표했다.
1962년의 리처드 벨먼, 알프레드 아이젠스타트 촬영. 그는 심벨, 포드, 무어에 이어 1958년에 이 최단 경로 방법을 발표했다.

직접 해 보기

앱을 열고 단계를 누르세요. 모든 간선은 단방향이고, 일부 길이는 음수입니다. 단계마다 고정된 순서로 간선 하나를 확인하며, 타일에는 현재 패스와 그 패스에서 바뀐 거리의 수가 나옵니다. 대개 곧 아무것도 바뀌지 않는 패스가 나와 탐색이 일찍 멈춥니다. 음수 사이클 추가를 체크하고, 확인용 패스가 사이클을 찾아 빨간색으로 그릴 때까지 패스마다 거리가 계속 줄어드는 모습을 지켜보세요.

자주 묻는 질문

벨만-포드 알고리즘의 시간 복잡도는?

노드 V개, 간선 E개에 대해 O(V · E)입니다. 패스는 많아야 V − 1번이고, 패스마다 모든 간선을 확인합니다. 일찍 멈추는 기법 덕분에 실제로는 훨씬 빠른 경우가 많고, 가장 좋은 경우에는 패스 한 번으로 충분합니다.

음수 사이클이란 무엇인가요?

간선 길이의 합이 0보다 작은 사이클입니다. 계속 돌면 경로를 원하는 만큼 짧게 만들 수 있으므로, 그 사이클을 거쳐 도달할 수 있는 모든 노드까지의 최단 거리는 정의되지 않습니다.

벨만-포드 알고리즘은 무방향 그래프에서도 작동하나요?

음수 간선이 없을 때만 그렇습니다. 무방향 음수 간선은 왔다 갔다 할 수 있으므로, 그 자체가 간선 두 개로 된 음수 사이클입니다. 음수가 아닌 간선이라면 작동하지만 다익스트라 알고리즘이 더 빠릅니다.

SPFA란 무엇인가요?

Shortest Path Faster Algorithm의 약자로, 큐를 써서 거리가 방금 바뀐 노드에서 나가는 간선만 다시 확인하는 벨만-포드의 변형입니다. 대개 훨씬 빠르지만 최악의 경우는 같습니다.

시도해 볼 준비가 되셨나요?

브라우저에서 PictorX를 엽니다. 설치가 필요 없고 시작하는 데 신용 카드가 필요하지 않습니다.

벨만-포드 알고리즘 해 보기