벨만포드 알고리즘: 가중치 그래프에서 최단 경로 찾기
지난 시간에는 그리디 알고리즘의 대표 주자인 Dijkstra 알고리즘을 통해 최단 경로를 찾는 방법을 살펴보았다. Dijkstra 알고리즘은 직관적이고 빠르지만, 음수 가중치를 가진 간선 (negative edge)이 존재하는 그래프에서는 최단 경로를 찾지 못하는 한계를 가지고 있었다. 왜냐하면, 그리디 알고리즘의 특성상 매 순간 최적의 선택을 하기 때문에, 음수 가중치를 가진 간선을 무한히 반복하여 지나가는 negative cycle에 빠질 수 있기 때문이다.
이러한 문제를 해결하기 위해 등장한 것이 바로 Bellman-Ford 알고리즘이다. Bellman-Ford 알고리즘은 다이나믹 프로그래밍 기법을 활용하여 음수 가중치를 가진 간선이 존재하더라도 최단 경로를 찾거나, 음수 사이클의 존재 여부를 판별할 수 있다.
Pseudocode
function BellmanFord(G, s)
// G: graph, s: start node
// 1. 초기화
for each vertex v in G
dist[v] = INF
dist[s] = 0
// 2. 완화
for i from 1 to |V(G)| - 1
for each edge (u, v) in G // 일부 u만 뽑는 것이 아니라, 모든 u에 대하여
if dist[v] > dist[u] + weight(u, v)
dist[v] = dist[u] + weight(u, v)
// 3. 음수 사이클 검사
for each edge (u, v) in G
if dist[v] > dist[u] + weight(u, v)
return "Negative cycle detected"
return dist
Bellman-Ford 알고리즘은 다음과 같은 단계로 작동한다.
초기화: 시작 노드
s에서 각 노드v까지의 최단 거리dist[v]를 무한대로 초기화한다. 단, 시작 노드s의 경우dist[s] = 0으로 설정한다.완화 (Relaxation): 그래프의 모든 간선
(u, v)에 대해 다음 과정을V-1번 반복한다. 여기서V는 그래프의 노드 개수를 의미한다.- 만약
dist[v] > dist[u] + weight(u, v)라면,dist[v]를dist[u] + weight(u, v)로 갱신한다. 즉, 현재 노드u를 거쳐 노드v로 가는 경로가 기존의 최단 경로보다 짧다면, 최단 경로를 갱신하는 것이다.
- 만약
음수 사이클 검사: 2번 단계를 한 번 더 반복한다. 만약 이 과정에서
dist[v]값이 갱신된다면, 그래프에 음수 사이클이 존재한다는 것을 의미한다.
Bellman-Ford 알고리즘 작동 예시 및 정확성 증명
이번에는 Bellman-Ford 알고리즘이 실제로 어떻게 작동하는지 구체적인 예시를 통해 살펴보고, 수학적 귀납법을 이용하여 알고리즘의 정확성을 증명해 보겠습니다.
이번에는 Bellman-Ford 알고리즘이 실제로 어떻게 작동하는지 구체적인 예시를 통해 살펴보고, 수학적 귀납법을 이용하여 알고리즘의 정확성을 증명해 보겠습니다.
작동 예시
다음과 같은 가중치 그래프를 고려해 보겠다. (지난 시간 Dijkstra와 같은 예시)
weighted graph
시작 노드를 A라고 가정하고 Bellman-Ford 알고리즘을 적용하면 다음과 같은 과정을 거친다.
초기화:
dist[A] = 0, dist[B] = INF, dist[C] = INF, dist[D] = INF, dist[E] = INF
1회 반복:
- 간선 (A, B)를 고려:
dist[B] = min(INF, 0 + 8) = 8
- 간선 (A, C)를 고려:
dist[C] = min(INF, 0 + 5) = 5
- 간선 (B, C)를 고려:
dist[C] = min(5, 8 + 3) = 5
- 간선 (B, D)를 고려:
dist[D] = min(INF, 8 + 1) = 9
- 간선 (C, E)를 고려:
dist[E] = min(INF, 5 + 9) = 14
- 간선 (D, E)를 고려:
dist[E] = min(14, 9 + 2) = 11
2회 반복:
- 간선 (A, B)를 고려:
dist[B] = min(8, 0 + 8) = 8
- 간선 (A, C)를 고려:
dist[C] = min(5, 0 + 5) = 5
- 간선 (B, C)를 고려:
dist[C] = min(5, 8 + 3) = 5
- 간선 (B, D)를 고려:
dist[D] = min(9, 8 + 1) = 9
- 간선 (C, E)를 고려:
dist[E] = min(11, 5 + 9) = 11
- 간선 (D, E)를 고려:
dist[E] = min(11, 9 + 2) = 11
3회 반복:
- ... (변화 없음)
4회 반복(총 n-1번):
- ... (변화 없음)
따라서 최종 결과는 다음과 같다.
dist[A] = 0, dist[B] = 8, dist[C] = 5, dist[D] = 9, dist[E] = 11
다음과 같은 가중치 그래프를 고려해 보겠다. (지난 시간 Dijkstra와 같은 예시)
 |
| weighted graph |
시작 노드를 A라고 가정하고 Bellman-Ford 알고리즘을 적용하면 다음과 같은 과정을 거친다.
초기화:
dist[A] = 0,dist[B] = INF,dist[C] = INF,dist[D] = INF,dist[E] = INF
1회 반복:
- 간선 (A, B)를 고려:
dist[B] = min(INF, 0 + 8) = 8 - 간선 (A, C)를 고려:
dist[C] = min(INF, 0 + 5) = 5 - 간선 (B, C)를 고려:
dist[C] = min(5, 8 + 3) = 5 - 간선 (B, D)를 고려:
dist[D] = min(INF, 8 + 1) = 9 - 간선 (C, E)를 고려:
dist[E] = min(INF, 5 + 9) = 14 - 간선 (D, E)를 고려:
dist[E] = min(14, 9 + 2) = 11
2회 반복:
- 간선 (A, B)를 고려:
dist[B] = min(8, 0 + 8) = 8 - 간선 (A, C)를 고려:
dist[C] = min(5, 0 + 5) = 5 - 간선 (B, C)를 고려:
dist[C] = min(5, 8 + 3) = 5 - 간선 (B, D)를 고려:
dist[D] = min(9, 8 + 1) = 9 - 간선 (C, E)를 고려:
dist[E] = min(11, 5 + 9) = 11 - 간선 (D, E)를 고려:
dist[E] = min(11, 9 + 2) = 11
3회 반복:
- ... (변화 없음)
4회 반복(총 n-1번):
- ... (변화 없음)
따라서 최종 결과는 다음과 같다.
dist[A] = 0,dist[B] = 8,dist[C] = 5,dist[D] = 9,dist[E] = 11
정확성 증명 (수학적 귀납법)
귀납 가정: i번째 반복 후, 모든 노드 v에 대해 dist[v]는 시작 노드 s에서 v까지 최대 i개의 간선을 사용하는 최단 경로의 길이와 같다.
기본 경우 (i = 0): 초기화 단계에서 dist[s] = 0이고, 다른 모든 노드에 대해 dist[v] = INF이므로 성립한다.
귀납 단계: i번째 반복 후 귀납 가정이 성립한다고 가정하자. (i+1)번째 반복 후에도 성립함을 보여야 한다.
(i+1)번째 반복에서 간선 (u, v)를 고려한다고 하자. 만약 dist[v] > dist[u] + weight(u, v)라면, dist[v]를 dist[u] + weight(u, v)로 갱신한다. 귀납 가정에 의해 dist[u]는 s에서 u까지 최대 i개의 간선을 사용하는 최단 경로의 길이이다. 따라서 dist[u] + weight(u, v)는 s에서 v까지 최대 (i+1)개의 간선을 사용하는 경로의 길이 중 하나이다.
만약 s에서 v까지 최대 (i+1)개의 간선을 사용하는 더 짧은 경로가 존재한다면, 그 경로는 u를 거치지 않아야 한다. 하지만 이는 i번째 반복 후 dist[v]가 s에서 v까지 최대 i개의 간선을 사용하는 최단 경로의 길이라는 귀납 가정에 모순된다. 따라서 (i+1)번째 반복 후에도 dist[v]는 s에서 v까지 최대 (i+1)개의 간선을 사용하는 최단 경로의 길이이다.
결론: 수학적 귀납법에 의해 Bellman-Ford 알고리즘은 모든 노드 v에 대해 시작 노드 s에서 v까지의 최단 경로를 정확하게 계산한다.
참고: 위 증명은 그래프에 음수 사이클이 없다는 가정 하에 성립한다. 음수 사이클이 존재하는 경우, 최단 경로가 정의되지 않을 수 있다.
귀납 가정: i번째 반복 후, 모든 노드 v에 대해 dist[v]는 시작 노드 s에서 v까지 최대 i개의 간선을 사용하는 최단 경로의 길이와 같다.
기본 경우 (i = 0): 초기화 단계에서 dist[s] = 0이고, 다른 모든 노드에 대해 dist[v] = INF이므로 성립한다.
귀납 단계: i번째 반복 후 귀납 가정이 성립한다고 가정하자. (i+1)번째 반복 후에도 성립함을 보여야 한다.
(i+1)번째 반복에서 간선 (u, v)를 고려한다고 하자. 만약 dist[v] > dist[u] + weight(u, v)라면, dist[v]를 dist[u] + weight(u, v)로 갱신한다. 귀납 가정에 의해 dist[u]는 s에서 u까지 최대 i개의 간선을 사용하는 최단 경로의 길이이다. 따라서 dist[u] + weight(u, v)는 s에서 v까지 최대 (i+1)개의 간선을 사용하는 경로의 길이 중 하나이다.
만약 s에서 v까지 최대 (i+1)개의 간선을 사용하는 더 짧은 경로가 존재한다면, 그 경로는 u를 거치지 않아야 한다. 하지만 이는 i번째 반복 후 dist[v]가 s에서 v까지 최대 i개의 간선을 사용하는 최단 경로의 길이라는 귀납 가정에 모순된다. 따라서 (i+1)번째 반복 후에도 dist[v]는 s에서 v까지 최대 (i+1)개의 간선을 사용하는 최단 경로의 길이이다.
결론: 수학적 귀납법에 의해 Bellman-Ford 알고리즘은 모든 노드 v에 대해 시작 노드 s에서 v까지의 최단 경로를 정확하게 계산한다.
참고: 위 증명은 그래프에 음수 사이클이 없다는 가정 하에 성립한다. 음수 사이클이 존재하는 경우, 최단 경로가 정의되지 않을 수 있다.
Bellman-Ford 알고리즘의 장단점
Bellman-Ford 알고리즘은 Dijkstra 알고리즘과 비교하여 다음과 같은 장점과 단점을 갖는다.
장점:
- 음수 가중치를 가진 간선이 존재하는 그래프에서도 최단 경로를 찾을 수 있다.
- 음수 사이클의 존재 여부를 판별할 수 있다.
단점:
- Dijkstra 알고리즘보다 시간 복잡도가 높다. (O(VE), V: 노드 개수, E: 간선 개수)
마무리
Bellman-Ford 알고리즘은 Dijkstra 알고리즘의 한계를 극복하고 음수 가중치를 가진 그래프에서도 최단 경로를 찾을 수 있는 강력한 알고리즘이다. 다이나믹 프로그래밍 기법을 활용하여 최단 경로를 점진적으로 계산하며, 음수 사이클의 존재 여부까지 판별할 수 있다는 점에서 그 활용도가 높다. (다이나믹 프로그래밍, 그리디 알고리즘에 대해서는 다음시간부터 자세히 알아보겠다)
추천글:
[알고리즘] Dijkstra algorithm의 모든 것 - definition, example, correctness, time complexity
(https://hyeondev.blogspot.com/2024/11/dijkstra-algorithm-definition-example.html)
