Bellman-Ford Algorithm

Computer Science/Algorithm

leta 2021. 7. 28. 00:57

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

가중치가 음수일 때도 사용 가능

다익스트라 알고리즘에 비해 느리므로 가중치가 모두 양수인 경우 굳이 벨만포드 사용할 필요 x. 다익스트라 쓰면 됨.

=> 그래프 정점 개수를 v라고 할 때 인접 간선을 검사하고

거리 값을 갱신 (갱신 과정은 v-1번으로 제한)

=> 그래프의 시작 정점에서 특정 정점까지 도달하기 위해 거치는

최대 간선 수: v-1개

=> v번째 간선이 추가되면 사이클이라고 판단

1. 시작 정점 결정

2. 시작 정점에서 각각 다른 정점까지의 거리 값을 무한대로 초기화

시작 정점이 a라면, dist[b] = a -> b의 거리

시작 정점 -> 시작 정점 : dist[a] = 0

3. 현재 정점에서 모든 인접 정점들을 탐색. 기존에 저장되어있는 인접 정점까지의 거리보다 현재 정점을 거쳐서 도달하는 거리가 더 짧을 경우 갱신.

4. 3번 과정을 v-1번 반복

5. 위 과정을 모두 마친 후 거리가 갱신되는 경우가 생긴다면 그래프에 음수 사이클이 존재한다는 뜻.