벨만 포드 (Bellman-Ford) 알고리즘
한 노드에서 다른 노드까지의 최단거리를 구하는 알고리즘
- 최단 경로를 찾는 알고리즘 (다익스트라, 벨만 포드, 플로이드 와샬)
- 가중치가 음수 일 때도 사용이 가능
- 다익스트라 알고리즘에 비해 느리므로 가중치가 모두 양수일 경우 다익스트라 알고리즘을 사용
- 경로 중에 음수 사이클이 존재하는 경우 확인 가능
음수 사이클 확인 방법
그래프의 정점의 개수를 라고 할 때, 인접 간선을 검사하고 거리 값을 갱신하는 과정은
음수 사이클을 확인하기 위해 V - 1번 대신 V번 검사를 하고 V번째에 값이 갱신 되었을 경우, 음수 사이클이 존재
벨만-포드 알고리즘 프로세스
1. 시작 정점을 결정
2. 시작 정점부터 다른 정점까지 거리 값 모두 무한대로 초기화 (시작 정점은 0으로 초기화)
3. 현재 정점의 모든 인접 정점들을 탐색하며, 기존에 기록된 인접 정점까지의 거리보다 현재 정점을 거쳐 인접 정점에
도달하는 거리가 더 짧다면 인접 정점까지의 거리를 갱신
4. 3번 과정을 번 반복한다.
5. 3번 과정을 한번 더 반복한 후 거리가 갱신되는 경우가 있다면 그래프에 음수 사이클이 발생한것을 확인 가능
ex) v1노드에서 시작
v1정점에 대한 모든 간선을 Relax
v2정점에 대한 모든 간선을 Relax
v2를 v2 -> v5로 이동하는 경우의 값 업데이트
v3정점에 대한 모든 간선을 Relax
v4정점에 대한 모든 간선을 Relax
v5정점에 대한 모든 간선을 Relax
변화가 없음
=> v2정점에서 사실상 종료
시간 복잡도
번 인접한 모든 간선들을 검사하는 과정을 거치기 때문
- 시간 복잡도가 였던 다익스트라 알고리즘에 비해서 복잡도가 더 크기는 하지만,
그래프에 음수 간선이 존재할 때 사용할 수 있다는 점,
음수 사이클 존재 여부를 판별할 수 있다는 점에서 유용하게 활용할 수 있는 알고리즘
'자료구조' 카테고리의 다른 글
| 레드 블랙 트리 (RED-Black Tree) (0) | 2021.05.15 |
|---|---|
| 브루트 포스 알고리즘 (brute force), 백트래킹 (Backtracing) 알고리즘 (0) | 2021.05.12 |
| 분할 정복 알고리즘 (Devide and Conquer) (0) | 2021.05.12 |
| 그리디 알고리즘 (Greedy Algorithm) (0) | 2021.05.12 |
| 해싱 (Hashing), 해시 충돌 (Hash Collision), 체이닝 (Chaining), 개방 주소법 (Open Addressing) (0) | 2021.05.12 |