티스토리 뷰

벨만 포드 (Bellman-Ford) 알고리즘

한 노드에서 다른 노드까지의 최단거리를 구하는 알고리즘

- 최단 경로를 찾는 알고리즘 (다익스트라, 벨만 포드, 플로이드 와샬)
- 가중치가 음수 일 때도 사용이 가능
- 다익스트라 알고리즘에 비해 느리므로 가중치가 모두 양수일 경우 다익스트라 알고리즘을 사용
- 경로 중에 음수 사이클이 존재하는 경우 확인 가능



음수 사이클 확인 방법


그래프의 정점의 개수를 라고 할 때, 인접 간선을 검사하고 거리 값을 갱신하는 과정은 
음수 사이클을 확인하기 위해 V - 1번 대신 V번 검사를 하고 V번째에 값이 갱신 되었을 경우, 음수 사이클이 존재

 

벨만-포드 알고리즘 프로세스

1. 시작 정점을 결정
2. 시작 정점부터 다른 정점까지 거리 값 모두 무한대로 초기화 (시작 정점은 0으로 초기화)
3. 현재 정점의 모든 인접 정점들을 탐색하며, 기존에 기록된 인접 정점까지의 거리보다 현재 정점을 거쳐 인접 정점에
   도달하는 거리가 더 짧다면 인접 정점까지의 거리를 갱신
4. 3번 과정을 번 반복한다.
5. 3번 과정을 한번 더 반복한 후 거리가 갱신되는 경우가 있다면 그래프에 음수 사이클이 발생한것을 확인 가능



ex) v1노드에서 시작

https://victorydntmd.tistory.com/104

v1정점에 대한 모든 간선을 Relax

https://victorydntmd.tistory.com/104

v2정점에 대한 모든 간선을 Relax
v2를 v2 -> v5로 이동하는 경우의 값 업데이트

https://victorydntmd.tistory.com/104

v3정점에 대한 모든 간선을 Relax
v4정점에 대한 모든 간선을 Relax
v5정점에 대한 모든 간선을 Relax

변화가 없음
=> v2정점에서 사실상 종료



시간 복잡도

번 인접한 모든 간선들을 검사하는 과정을 거치기 때문
- 시간 복잡도가 였던 다익스트라 알고리즘에 비해서 복잡도가 더 크기는 하지만,
   그래프에 음수 간선이 존재할 때 사용할 수 있다는 점,
   음수 사이클 존재 여부를 판별할 수 있다는 점에서 유용하게 활용할 수 있는 알고리즘



 

728x90
댓글
댓글쓰기 폼
공지사항