[알고리즘] DP (3) - 벨만포드(Bellman-Ford) 알고리즘

 

 

 

 

 

🧐 최단 경로 문제

그래프 G = (V, E) 상에서 정점 u에서 v로의 가장 짧은 path의 길이를 구하는 문제를 의미합니다.

유명한 방법으로는 다익스트라 알고리즘이 있습니다.

그러나 다익스트라 알고리즘은 음수 가중치를 가지는 간선이 없는 그래프에 대해서만 올바르게 동작한다는 제약이 있습니다.

 

 

 

 

 

 

 

 

 

 

 

🧐 Bellman-Ford 알고리즘

최단 경로 문제를 해결하는 dp 기반의 알고리즘입니다.

 

다익스트라 알고리즘과 마찬가지로 시작 정점 s에서 그래프 G에 존재하는 다른 모든 정점으로의 최단경로를 구하며, 매 단계마다 해당 최단거리의 길이를 업데이트하며 진행되는 알고리즘입니다.

 

기본적으로는 방향(directed) 그래프를 가정하지만, 무방향 그래프에 대해서도 이를 방향 그래프로 생각하여 적용할 수 있습니다.

벨만포드 알고리즘은 가중치가 음수인 간선이 존재하는 경우에도 올바르게 동작합니다.

그러나 negative cycle을 가진다면 올바르게 동작하지 않으며,
벨만포드 알고리즘의 성질을 이용하여 negative cycle에 대한 검출을 진행할 수 있습니다.

 

 

기본적인 아이디어는 다음과 같습니다.

dist(u) 를 시작점 s로부터 정점 u까지의 에서 실제 최단경로의 길이라 하고,
dist(i, u) 를 edge를 i개 이하로 사용하면서 정점 s에서 u로 가는 최단경로의 길이라 하겠습니다.

 

 

이때 중요한 특징은 다음과 같습니다.

모든 i < j 에 대하여
$$dist(u) \leq dist(j, u) \leq dist(i, u)$$

따라서 negetive cycle이 없는 경우 dist(u) = dist(|V| - 1 , u)가 성립합니다.

 

 

 

 

 

 

 

 

 

🧐 왜 |V| - 1일까?

최단 경로는 walk가 아니라 path입니다.

path는 정점을 반복해서 방문하지 않기 때문에, path에서는 최대 |V|개의 정점을 반복할 수 있고, 해당 path에 존재하는 간선의 개수는 |V| - 1 개이기 때문입니다.

 

 

 

 

 

 

 

 

 

 

 

 

🧐 Recurrence Relation

 

Base Case

i = 1인 경우, dist(0, s) = 0 , 나머지는 dist(0, v) = 무한대

 

 

 

귀납 단계

dist(i, v) > dist(i, u) + w(u, v) 를 만족하는 모든 간선 (u, v)들 중, 오른쪽 항을 가장 작게 만드는 간선(u', v)가 있다면

dist(i + 1, v) = dist(i, u') + w(u', v) 입니다.

이때 위를 만족하는 간선이 존재하지 않는다면 dist(i + 1, v) = dist(i, v) 입니다.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

🧐 벨만포드 알고리즘의 과정

1. 총 n-1 번 반복되며, i번째 반복이 끝날 때마다 그래프 G의 모든 정점 v에 대하여
dist(i, v) 를 dist(v)에 저장합니다.

2. 시작할 때 dist의 값을 시작점 s에 대해서는 dist(0, s) = 0으로 설정하고, 
나머지 정점들에 대해서는 dist(0, v) = '무한대'로 설정합니다.

3. 이후 i번째 반복마다 모든 간선(u, v)에 대해 다음 작업을 반복합니다.

v로 도달하는 최단경로보다, u로 도달하는 최단경로 + u에서 v로의 간선의 가중치가 더 작은 경우, 즉
dist(v) > dist(u) + w(u, v)인 경우 dist(v) 를 dist(u) + w(u, v)로 업데이트합니다.
(이때 w(u, v)는 간선(u, v)의 가중치입니다.)

 

 

 

 

 

 

 

 

 

 

🧐 예시

 

시작점은 0, 나머지 정점들에 대해서는 무한대가 됩니다.

 

 

dist(A)['무한대'] 보다 dist(S)[0] + w(S, A)[10]가 더 작으므로 dist(A)를 dist(S) + w(S, A)로 바꿔주었습니다.

G도 마찬가지입니다.

 

 

 

 

 

3번째 반복을 보면 B의 경우에는 dist(2, E) + w(E, B)의 값인 10으로 업데이트 되는 것을 알 수 있습니다.

이때 dist(3, E)의 값이 8이므로, dist(3, E) + w(E, B)를 하면 6이 되지만, 반드시 이전 반복에서 업데이트 된 값만을 사용해야 합니다.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

🧐 수도코드

 

 

 

 

 

 

 

 

🧐 시간 복잡도

n번 반복 : $O(n)$

매 반복마다 모든 간선들을 확인하여 dist 값을 업데이트 $O(m)$

따라서 $O(nm)$

 

 

 

 

 

 

 

 

 

 

 

 

🧐 실제 최단 경로를 구하는 방법

위 알고리즘에서 dist(v)를 dist(u) + w(u, v) 로 업데이트 할 때마다 pre(v) = u로 설정합니다.

실제 경로는 알고리즘의 종료 후 v에서부터 pre(v)를 역으로 거슬러 올라가며 역추적할 수 있습니다.

 

 

 

 

 

 

 

 

 

 

 

 

🧐 음의 사이클 판별

음의 사이클이 있는 경우 밸만포드 알고리즘은 해당 음의 사이클을 계속해서 돌다가 n-1번의 반복이 종료된 뒤 실제 path가 아닌 다른 값을 반환하게 됩니다.

 

즉 이 성질을 통해 밸만포드 알고리즘으로 그래프에 음의 사이클이 존재하는지 판별할 수 있습니다.

n-1 번째 반복 이후 n번째 반복을 추가로 수행하여 dist 값이 업데이트 되는 경우 음의 사이클이 존재합니다.