벨만포드 알고리즘

벨만-포드 알고리즘 개요
벨만-포드(Bellman-Ford) 알고리즘은 그래프에서 음수 가중치가 포함된 최단 경로를 찾을 때 사용되는 알고리즘이다. 다익스트라 알고리즘과 다르게 음수 가중치를 허용하지만, 음수 사이클(negative cycle)이 존재하면 경로를 찾을 수 없다.

벨만-포드 알고리즘의 특징
음수 가중치를 허용

음수 사이클 감지 가능

시간 복잡도:
𝑂
(
𝑉
𝐸
)
O(VE) (V는 정점 개수, E는 간선 개수)

다익스트라보다 느리지만, 음수 가중치를 처리해야 할 때 유용

벨만-포드 알고리즘 동작 과정
모든 거리(distance) 값을 무한대(∞)로 초기화하고, 시작 노드는 0으로 설정한다.

V-1번 반복하면서 모든 간선 (u, v, w)에 대해 Relaxation(완화) 수행

만약 distance[u] + w < distance[v] 이라면, distance[v]를 업데이트

추가로 한 번 더 반복하여 Relaxation이 발생하면 음수 사이클이 존재함을 감지