벨만-포트(bellman-ford-moore) 알고리즘은 그래프에서 최단 거리를 구하는 알고리즘으로 주요 특징은 다음과 같다.
기능 | 특징 | 시간 복잡도(노드 수 : V, 에지 수 : E) |
---|---|---|
특정 출발 노드에서 다른 모든 노드까지의 최단 경로 탐색 | - 음수 가중치가 있어도 수행할 수 있음 - 전체 그래프에서 음수 사이클의 존재 여부를 판단할 수 있음 | O(VE) |
벨만-포트 알고리즘은 에지를 중심으로 동작하므로 그래프를 에지 리스트로 구현한다. 또한 최당 경로 배열은 출발 노드는 0, 나머지 노드는 무한대로 초기화한다.
최단 거리 배열에서 업데이트 반복 횟수는 노드 개수 - 1 이다. 노드 개수가 N이고, 음수 사이클이 없을 때 특정 두 노드의 최단 거리를 구성할 수 있는 에지의 최대 개수는 N - 1이기 때문이다. 특정 에지 E = (s, e, w)에서 다음 조건을 만족하면 업데이트를 실행한다.
음수 사이클 유무를 확인하기 위해 모든 에지를 한 번씩 다시 사용해 업데이트되는 노드가 발생하는지를 확인한다. 만약 업데이트되는 노드가 있다면 음수 사이클이 있다는 뜻이 되고, 2단계에서 도출한 정답 배열이 무의미하고 최단 거리를 찾을 수 없는 그래프라는 뜻이 된다. 음수 사이클이 존재하면 이 사이클을 무한하게 돌수록 가중치가 계속 감소하므로 최단 거리를 구할 수 없다.
실제 알고리즘 코딩 테스트에선 벨만-포트 알고리즘을 사용해 최단 거리를 구하는 문제보다 음수 사이클을 판별하는 문제가 더 빈번하게 출제된다. 따라서 마지막에 한 번 번 더 모든 에지를 사용해 업데이트되는 노드가 존재하는지 확인해야 한다.
- Do it! 알고리즘 코딩테스트 자바 편