토픽 28 / 82

Bellman-Ford 알고리즘

가중치가 음수일 수 있는 그래프에서 한 정점에서 다른 모든 정점까지의 최단 경로를 찾는 동적 프로그래밍 기반 알고리즘

목적: 음수 가중치 처리, 음수 사이클 탐지

특징: 동적 프로그래밍, 음수 가중치 가능, 음수 사이클 탐지

동작 상세

V-1번 반복의 원리: i번째 반복 후 최대 i개 간선을 사용하는 최단 경로가 확정됨. 최단 경로는 V개 정점을 거치므로 최대 V-1개 간선을 포함

시간 복잡도: O(VE) - V-1번 × E개 간선

공간 복잡도: O(V) - 거리 배열

최적화: 특정 반복에서 갱신이 없으면 조기 종료 가능 (이미 모든 최단 경로 확정)

장점: 음수 가중치 처리, 음수 사이클 탐지, 단순 구현 (3중 for문), 분산 시스템에 적합

단점: 느림(O(VE)), Dijkstra보다 비효율, 밀집 그래프에서 O(V³)

적용사례: 음수 가중치 그래프, 통화 환전(음수 사이클=차익거래 기회 탐지), 네트워크 라우팅(RIP/거리 벡터 프로토콜)

비교: Bellman-Ford(음수/느림/O(VE)) vs Dijkstra(양수/빠름/O((V+E) log V))

연관: 동적 프로그래밍, 최단 경로, Dijkstra, 음수 사이클, SPFA