Motivation
Coddy의 벨만-포드 알고리즘 - 그래프 알고리즘 코스 레슨 — 9개 중 2번째.
벨만-포드(Bellman-Ford) 알고리즘은 완화(relaxation)라는 하나의 연산을 기반으로 구축되었습니다. 가중치가 w인 간선 u -> v에 대해, u를 거쳐가는 것이 더 저렴하다면(dist[u] + w < dist[v]), dist[v]를 업데이트합니다. 이 과정을 모든 간선에 대해 반복적으로 수행합니다.
왜 벨만-포드를 배워야 할까요?
- 음수 가중치: 리베이트나 통화 차익 거래와 같이 비용이 음수가 될 수 있는 경우처럼, 다익스트라(Dijkstra) 알고리즘이 작동하지 않는 곳에서도 작동합니다.
- 음수 사이클 감지: 한 번의 추가적인 완화 과정을 통해 전체 가중치가 음수인 사이클을 찾아낼 수 있습니다.
- 단순함: 우선순위 큐(priority queue)가 필요 없으며, 단지 반복적인 간선 완화만 수행하면 됩니다.
대신 속도와 트레이드오프가 있습니다. O(V * E)로, 다익스트라의 O((V + E) log V)보다 느립니다.
직접 해보기
이 레슨에는 코드 챌린지가 없습니다.
실력 점검이 레슨에는 짧은 퀴즈가 포함되어 있습니다. 레슨을 시작해 문제를 풀고 진행 상황을 기록하세요.
