벨먼-포드 알고리즘
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.
1. 개요
벨만-포드 알고리즘은 그래프에서 단일 시작점으로부터 다른 모든 정점까지의 최단 경로를 찾는 데 사용되는 알고리즘이다. 다익스트라 알고리즘과 유사하게 완화 과정을 사용하지만, 모든 간선을 여러 번 완화하는 방식으로 작동한다. 벨만-포드 알고리즘은 음수 가중치를 가진 간선이 있는 그래프에도 적용할 수 있지만, 음수 사이클이 존재하면 최단 경로를 찾을 수 없으며, 음수 사이클 탐지에 활용될 수 있다. 시간 복잡도는 O(|V| * |E|)이며, 여기서 |V|는 정점의 수, |E|는 간선의 수이다. 라우팅 프로토콜, 특히 거리 벡터 라우팅 프로토콜에서 사용된다. 조기 종료, 완화 단계 수 줄이기, 옌(Yen)의 개선, 배니스터와 엡스타인(Bannister & Epstein)의 개선, 파이먼(Peyman)의 개선 등 다양한 방식으로 개선될 수 있다.
더 읽어볼만한 페이지
- 다항 시간 문제 - 플로이드-워셜 알고리즘
플로이드-워셜 알고리즘은 동적 계획법의 일종으로, 그래프 내의 모든 정점 쌍 간의 최단 경로를 찾아 시간 복잡도 O(N^3)으로 계산하며, 유향 그래프의 최단 경로 탐색 등 다양한 문제에 적용된다. - 다항 시간 문제 - 크러스컬 알고리즘
크러스컬 알고리즘은 그래프의 최소 신장 트리를 찾는 알고리즘으로, 간선들을 가중치 순으로 정렬하고 사이클을 형성하지 않는 간선들을 추가하여 최소 신장 트리를 구성하며 시간 복잡도는 O(E log V) 또는 O(E α(V))이다. - 동적 계획법 - 배낭 문제
배낭 문제는 주어진 배낭 용량 내에서 물건들의 가치 합을 최대화하는 조합 최적화 문제로, 물건을 쪼갤 수 있는지, 개수 제한이 있는지에 따라 다양한 변형이 있으며, 동적 계획법, 탐욕 알고리즘 등으로 해결하고, NP-완전 문제에 속하며 자원 할당 문제 등에 응용된다. - 동적 계획법 - 차원의 저주
차원의 저주는 고차원 공간에서 데이터 분석 및 모델링의 어려움을 나타내는 현상으로, 계산 시간 증가, 수치 오차 발생, 조합 폭발 등의 문제점을 야기한다. - 그래프 알고리즘 - 페이지랭크
페이지랭크는 래리 페이지와 세르게이 브린이 개발한 알고리즘으로, 하이퍼링크로 연결된 문서 집합에서 웹 페이지의 상대적 중요도를 측정하며, 링크를 투표로 간주하여 페이지 순위를 재귀적으로 결정하고, 구글 검색 엔진의 초기 핵심 알고리즘으로 활용되었으며, 다양한 분야에서 활용된다. - 그래프 알고리즘 - 너비 우선 탐색
너비 우선 탐색은 그래프 탐색 알고리즘으로, 큐 자료구조를 사용하여 시작 노드에서 인접한 노드들을 우선적으로 탐색하며, 가중치가 없는 그래프에서 최단 경로를 찾는 데 유용하고 다양한 분야에 활용된다.
| 벨먼-포드 알고리즘 | |
|---|---|
| 알고리즘 개요 | |
| 분류 | 단일 출발점 최단 경로 문제(가중치가 있는 방향 그래프) |
| 자료 구조 | 그래프 |
| 최악 시간 복잡도 | Θ(|V| |E|) |
| 최선 시간 복잡도 | Θ(|E|) |
| 공간 복잡도 | Θ(|V|) |
2. 알고리즘
벨먼-포드 알고리즘은 다익스트라 알고리즘과 유사하게 완화(relaxation) 과정을 통해 최단 거리를 찾는다. 다익스트라 알고리즘이 아직 처리되지 않은 가장 가까운 정점을 탐욕적으로 선택하는 반면, 벨먼-포드 알고리즘은 모든 간선에 대해 완화 작업을 반복한다. 반복 횟수는 그래프의 정점 개수 |*V*| - 1번이다. 이러한 접근 방식은 다익스트라 알고리즘보다 더 넓은 범위의 입력에 적용될 수 있게 한다.
두 알고리즘 모두 각 정점까지의 근사 거리는 항상 실제 거리의 과대 평가이며, 이전 값과 새로 발견된 경로의 길이 중 더 작은 값으로 대체되는 완화를 통해 진행된다.
벨먼-포드 알고리즘의 실행 시간은 *O*(|*V*| · |*E*|)이며, |*V*|와 |*E*|는 각각 정점 수와 간선 수이다.
알고리즘은 시작점까지의 거리를 0으로 초기화하고 다른 모든 노드를 무한대로 초기화한다. 그런 다음 모든 간선에 대해, 대상까지의 거리가 해당 간선을 사용함으로써 줄어들 수 있다면 거리가 새로운 더 낮은 값으로 업데이트된다.
핵심은 모든 루프에서 모든 간선을 스캔하는 루프이다. 음수 사이클이 없으면 최단 경로 상의 각 정점은 기껏해야 1번만 나타나므로, 반복을 통해 최단 거리가 정확하게 그래프 전체에 전파된다. 가중치가 양수임을 전제로 하는 구조상의 가정을 기반으로 하는 탐욕법적 방법과는 달리, 이 방법은 보다 범용적이다.
알고리즘 구현 시 일반적인 개선 사항은 2단계 반복에서 간선 완화에 실패할 때 조기에 반환하는 것이다. 이는 모든 최단 경로가 발견되었음을 의미하며, 음수 사이클이 없음을 뜻한다. 이 경우 알고리즘의 복잡성은 에서 로 감소한다. 여기서 은 그래프에서 최단 경로의 최대 길이이다.
2. 1. 의사 코드 (Pseudo-code)
'''procedure''' BellmanFord(''list'' vertices, ''list'' edges, ''vertex'' source)''// 이 구현에서는 그래프를 정점(vertices)과 간선(edges)의 리스트로 나타낸다.''
''// 1단계: 그래프 초기화''
'''for each''' vertex v in vertices:
'''if''' v '''is''' source '''then''' v.distance := 0
'''else''' v.distance := '''infinity'''
v.predecessor := '''null'''
''// 2단계: 간선 완화 반복''
'''for''' i '''from''' 1 '''to''' size(vertices) - 1:
'''for each''' edge uv in edges: ''// uv는 u에서 v로 향하는 간선''
u := uv.source
v := uv.destination
'''if''' v.distance > u.distance + uv.weight:
v.distance := u.distance + uv.weight
v.predecessor := u
''// 3단계: 음수 가중치 사이클 확인''
'''for each''' edge uv in edges:
u := uv.source
v := uv.destination
'''if''' u.distance + uv.weight < v.distance:
'''error''' "Graph contains a negative-weight cycle"
2. 2. 알고리즘의 정당성 증명
수학적 귀납법으로 알고리즘의 정확성을 증명할 수 있다.[2]'''정리'''. ''for'' 루프를 ''i''번 반복한 후,
- Distance(''u'')가 무한대가 아니라면, 이는 ''s''에서 ''u''까지의 어떤 경로의 길이와 같고,
- ''s''에서 ''u''까지 최대 ''i''개의 간선이 있는 경로가 있다면, Distance(u)는 ''s''에서 ''u''까지 최대 ''i''개의 간선이 있는 최단 경로의 길이보다 작거나 같다.
'''증명'''. 귀납법의 기본 사례로,
i=0이고 ''for'' 루프가 처음 실행되기 전의 순간을 고려한다. 소스 정점의 경우, source.distance = 0인데, 이는 올바르다. 다른 정점 ''u''의 경우, u.distance = '''무한대'''인데, 이는 0개의 간선으로 ''source''에서 ''u''까지의 경로가 없기 때문에 올바르다.귀납적인 경우, 먼저 첫 번째 부분을 증명한다. 정점의 거리가
v.distance := u.distance + uv.weight로 업데이트되는 순간을 고려한다. 귀납적 가설에 따르면 u.distance는 ''source''에서 ''u''까지의 어떤 경로의 길이이다. 그러면 u.distance + uv.weight는 ''source''에서 ''u''까지의 경로를 따르고 ''v''로 가는 ''source''에서 ''v''까지의 경로의 길이이다.두 번째 부분의 경우, 최대 ''i''개의 간선이 있는 ''source''에서 ''v''까지의 최단 경로 ''P''를 고려한다(둘 이상일 수 있음). 이 경로에서 ''v'' 이전의 마지막 정점을 ''u''라고 하자. 그러면 ''source''에서 ''u''까지의 경로 부분은 최대 ''i''-1개의 간선이 있는 ''source''에서 ''u''까지의 최단 경로이다. 왜냐하면 그렇지 않다면, 최대 ''i''-1개의 간선이 있는 ''source''에서 ''u''까지의 더 짧은 경로가 있어야 하고, 그러면 간선 ''uv''를 이 경로에 추가하여 ''P''보다 더 짧은 최대 ''i''개의 간선이 있는 경로를 얻을 수 있기 때문이다. (모순) 귀납적 가설에 따르면, ''i''−1 반복 후
u.distance는 ''source''에서 ''u''까지의 이 경로의 길이보다 작거나 같다. 따라서 uv.weight + u.distance는 ''P''의 길이보다 작거나 같다. ''i''번째 반복에서 v.distance는 uv.weight + u.distance와 비교되고, uv.weight + u.distance가 더 작으면 그것과 같게 설정된다. 따라서 ''i'' 반복 후 v.distance는 ''P''의 길이, 즉 최대 ''i''개의 간선을 사용하는 ''source''에서 ''v''까지의 최단 경로의 길이보다 작거나 같다.음수 가중치 사이클이 없으면 모든 최단 경로는 각 정점을 최대 한 번 방문하므로, 단계 3에서 더 이상 개선할 수 없다. 반대로, 개선할 수 없다고 가정한다. 그러면 정점 ''v''[0], ..., ''v''[''k''−1]이 있는 모든 사이클에 대해,
v[i].distance <= v[i-1 (mod k)].distance + v[i-1 (mod k)]v[i].weight사이클을 합산하면, ''v''[''i''].distance와 ''v''[''i''−1 (mod ''k'')].distance 항이 상쇄되어 다음이 남는다.
0 <= sum from 1 to k of v[i-1 (mod k)]v[i].weight즉, 모든 사이클은 음이 아닌 가중치를 갖는다.
3. 음수 사이클 찾기
벨먼-포드 알고리즘은 음수 가중치를 가진 간선이 있는 그래프에서도 최단 경로를 찾을 수 있지만, 그래프에 음수 사이클이 있으면 문제가 발생한다. 음수 사이클은 계속해서 순환하며 가중치를 무한히 감소시킬 수 있기 때문이다.
벨먼-포드 알고리즘은 이러한 음수 사이클의 존재를 감지하고 종료할 수 있다. 알고리즘의 3단계에서 모든 간선 (u, v)에 대해 거리[u] + w < 거리[v] 인 경우가 있다면, 이는 음수 사이클이 존재함을 의미한다.[1]
이때, 음수 사이클에 속한 정점을 찾기 위해, `방문됨` 배열을 활용하거나, 또는 다른 사이클 찾기 알고리즘을 사용할 수 있다.
알고리즘이 음수 사이클을 발견하면 종료되므로, 이를 사이클 제거 기법과 같은 네트워크 흐름 분석에 응용할 수 있다.[1]
4. 라우팅에서의 응용
벨먼-포드 알고리즘의 분산 버전은 라우팅 정보 프로토콜(RIP)과 같은 거리 벡터 라우팅 프로토콜에서 사용된다. 이 알고리즘은 인터넷 서비스 제공업체가 일반적으로 소유하는 IP 네트워크 모음인 자율 시스템(AS) 내의 여러 노드(라우터)가 관여하기 때문에 분산되어 있다.
이 알고리즘은 다음 단계로 구성된다.
| 단계 | 설명 |
|---|---|
| 1 | 각 노드는 자신과 AS 내의 다른 모든 노드 간의 거리를 계산하고 이 정보를 표로 저장한다. |
| 2 | 각 노드는 자신의 표를 모든 인접 노드로 보낸다. |
| 3 | 노드는 인접 노드로부터 거리 표를 받으면 다른 모든 노드까지의 최단 경로를 계산하고 변경 사항을 반영하도록 자신의 표를 업데이트한다. |
이 설정에서 벨먼-포드 알고리즘의 주요 단점은 다음과 같다.
- 확장성이 좋지 않다.
- 네트워크 구성의 변경 사항이 노드별로 전파되므로 빠르게 반영되지 않는다.
- 무한대로 세는 문제 (링크 또는 노드 실패로 인해 노드에 일부 다른 노드 세트에서 도달할 수 없게 되면 해당 노드는 영원히 해당 노드까지의 거리에 대한 추정치를 점진적으로 증가시킬 수 있으며 그동안 라우팅 루프가 발생할 수 있다.)
5. 개선 사항
벨만-포드 알고리즘은 다음과 같은 방법으로 개선될 수 있다.
- 조기 종료: 알고리즘의 주요 루프에서 더 이상 거리 값의 변화가 없다면, 남은 반복을 수행해도 결과는 바뀌지 않으므로 알고리즘을 즉시 종료할 수 있다. 이 방법은 최악의 경우 시간 복잡도를 에서 로 줄여준다. 여기서 은 그래프에서 최단 경로의 최대 길이이다.
- 무어(Moore)의 개선: 알고리즘의 각 반복에서 완화해야 하는 간선의 수를 줄이는 방법이다. 어떤 정점 ''v''의 거리 값이 ''v''에서 시작하는 간선이 마지막으로 완화된 이후 변경되지 않았다면, ''v''에서 시작하는 간선을 다시 완화할 필요가 없다. 이 방법은 밀집 그래프에서 상당한 시간 절약을 가져온다. 중국에서는 1994년에 판딩 돤이 이 알고리즘을 재발견하여 "최단 경로 더 빠른 알고리즘"으로 대중화되었다.[4]
- 옌(Yen)의 개선:[9] 모든 정점에 임의의 선형 순서를 할당한 다음, 모든 간선을 두 개의 부분 집합으로 나눈다. 첫 번째 부분 집합 ''Ef''는 ''i'' < ''j''인 모든 간선 (''vi'', ''vj'')을 포함하고, 두 번째 부분 집합 ''Eb''는 ''i'' > ''j''인 간선 (''vi'', ''vj'')을 포함한다. 각 정점은