벨만 포드(Bellman-Ford)
그래프에서 최단 거리를 구하는 알고리즘 중 하나이다.
특정 출발 노에서 다른 모든 노드까지의 최단 경로를 탐색한다.
다익스트라와 비슷하지만 다른 점은 벨만 포드 알고리즘은 음수 가중치 에지가 있어도 수행할 수 있다는 점이다.
따라서, 벨만 포드 알고리즘은 최단 경로를 구하는 문제 보다는 전체 그래프에서 음수 사이클의 존재 여부를 판단하는 문제로 출제된다.
시간 복잡도는 O(VE) V: 노드 수, E: 에지 수
벨만 포드 핵심 원리
1. 에지 리스트로 그래프를 구현하고 최단 경로 리스트 초기화하기
벨만-포드 알고리즘은 에지를 중심으로 동작하므로 에지 리스트로 구현한다.
최단 경로 리스트(정답 리스트)에서 출발 노드는 0, 나머지는 무한대로 초기화한다. (출발 노드는 무한대가 되면 안된다)
2. 모든 에지를 확인해 정답 리스트 업데이트하기
노드 개수가 N이고, 음수 사이클이 없을 때 특정 두 노드의 최단 거리를 구성할 수 있는 에지의 최대 개수는 N - 1개 이다.
따라서, 최단 거리 리스트에서 업데이트 반복 횟수는 노드 개수 -1 번 반복하게 되고 위 예제와 같이 총 노드의 개수가 5개로 4번의 반복을 통해 정답 리스트를 만들 수 있다.
업데이트 반복 횟수가 K번이라면 해당 시점에 정답 리스트의 값은 시작점에서 K개의 에지를 사용 했을 때 각 노드에 대한 최단 거리다.
벨만 포드의 핵심은 N - 1번의 에지 사용 횟수를 반복하며 최단 거리 리스트를 완성하고, 그 후 마지막으로 해당 그래프에 음수 사이클이 존재하는지 N번 확인해야 한다.
업데이트 조건과 방법
D[s] != ∞ && D[e] > D[s] + w 일 때 D[e] = D[s] + w로 리스트의 값을 업데이트 한다.
3. 음수 사이클 유무 확인하기
음수 사이클 유무를 확인하기 위해 모든 에지를 한 번씩 다시 사용하여 업데이트가 발생하는 노드가 있는지 확인한다.
만약 업데이트되는 노드가 있다면 음수 사이클이 있다는 뜻이고 위의 예시 처럼 도출된 정답 리스트가 무의미하고 최단 거리를 찾을 수 없는 그래프가 된다.
마지막 정답 리스트에서 노드 5번에 해당하는 값 11을 사용하여 계산해보면
D[5] != ∞ && D[4] > D[5] + (-2) == 10 != ∞ && 11 > 10 - 2
업데이트 방법을 통해 4번 노드의 값을 9로 변경하게 되면서 업데이트가 발생하게 된다. 따라서, 해당 그래프는 음수 사이클이 존재하여 최단 거리를 구할 수 없는 그래프인 것을 확인할 수 있다.
'CS > 알고리즘' 카테고리의 다른 글
| 알고리즘 - 최소 신장 트리(MST, Minimum Spanning Tree) (0) | 2023.08.15 |
|---|---|
| 알고리즘 - 플로이드-워셜(Floyd-warshall) (0) | 2023.08.15 |
| 알고리즘 - 다익스트라(Dijkstar) (0) | 2023.08.15 |
| 알고리즘 - 위상 정렬 (0) | 2023.08.14 |
| 알고리즘 - 유니온 파인드 (0) | 2023.08.14 |
