[자료구조][알고리즘] Bellman-Ford Algorithm(벨먼-포드 알고리즘)

1. Bellman-Ford Algorithm이란?

Bellman-Ford Algorithm(벨먼-포드 알고리즘)은 각 edge에 cost가 있는 direct graph에서 한 vertex에서 출발하여 다른 모든 vertex까지 도달하는 최단 경로를 찾는 알고리즘(Single Source All Destination)이다. 벨먼-포드 알고리즘은 다익스트라 알고리즘과 달리 edge의 cost가 음수이거나 음수 cycle이 존재하는 경우에도 최단 경로를 보장한다.

2. Bellman-Ford Algorithm의 Pseudo code

//initialize d(*, 0)
d(s, 0) = 0;
d(v, 0) = infinity, v != s;
//compute d(*, k), 0 < k < n
for (int k = 1; k < n; k++)
{
	d(v, k) = d(v, k - 1), 1 <= v <= n;
    for (each edge (u, v))
    	d(v, k) = min{d(v, k), d(u, k - 1) + cost(u, v)}
}

3. 예시

위 그림과 같은 그래프가 있을 때, 1 노드에서 출발하여 각 노드에 이르는 최단 경로를 찾고자 한다. $d(v, k)$는 k개의 edge 이내로 1 노드에서 v 노드에 도착하는 최소 cost의 합을, $p(v, k)$는 $d(v, k)$의 경로에서의 도착 노드 바로 이전 노드이다. 위 표에서 가로축은 $v$, 세로축은 $k$이다.
다익스트라 알고리즘과 비슷하지만, 다익스트라 알고리즘은 노드를 기반으로 최단 경로를 탐색하지만 벨먼-포드 알고리즘은 간선을 기반으로 최단 경로를 탐색한다는 차이점이 있다. 벨먼-포드 알고리즘은 음의 cycle이 있는 경우를 대비하기 위해 모든 간선을 여러 번 검사하면서 경로를 갱신한다. 이때, DP(dynamic programming, 동적 프로그래밍) 방식을 사용한다.
벨먼-포드 알고리즘의 핵심은 $d(v,k)$를 기존 $d(v,k)$, $d(u, k-1)+cost(u,v)$ 중 작은 것으로 갱신하는 것이다.

4. 시간 복잡도

• 인접 행렬 사용 시: $O(n^3)$
• 인접 리스트 사용 시: $O(ne)$