티스토리 뷰
이번에 배워볼 알고리즘은 벨만 포드 알고리즘(Bellman-Ford Algorithm)이다. 이 알고리즘 또한 이전에 배운 다익스트라 알고리즘처럼 그래프에서 한 정점에서 다른 모든 정점으로 가는 최단 경로를 구할 수 있는 알고리즘이다.
벨만 포드 알고리즘은 다익스트라 알고리즘보다 시간이 더 걸리지만 음의 간선이 존재해도 최단 경로를 찾을 수 있는 알고리즘이다.
벨만 포드 알고리즘은 다이나믹 프로그래밍이라고 할 수 있다. 그 이유는 매번 저장해놓은 최소 비용을 이용해서 새로운 최소 비용으로 갱신하기 때문이다.
벨만 포드 알고리즘이 다익스트라 알고리즘보다 시간이 오래 걸리는 이유는 다익스트라는 최소 비용을 가지는 간선만 우선적으로 뽑으면서 경우의 수를 줄여가며 비용을 갱신하였다. 하지만 벨만 포드 알고리즘은 음의 간선 때문에 모든 경우의 수를 다 탐색하는 알고리즘이다.
벨만 포드 알고리즘의 동작 원리는 다음과 같다.
- 시작 정점을 선택한다.
- 모든 간선들을 탐색하면서, 시작 정점에서 다른 정점까지의 거리가 INF가 아니라면 거리를 갱신한다. 이 과정을 정점의 수-1번만큼 진행한다.
- 마지막으로 2번을 수행한다.
나는 U에서 시작한다고 가정했다.
https://sorjfkrh5078.tistory.com/30