Bellman-Ford Algorithm

Bellman-Ford Algorithm

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

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

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

 

 

• Bellman-Ford 알고리즘의 특징

1. 음수 가중치가 있는 그래프의 시작 정점에서 다른 정점까지의 최단 거리를 구할 수 있다.
2. 음수 사이클 존재 여부를 알 수 있다.

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

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

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

               최대 간선 수:  v-1개

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

 

 

• Bellman-Ford 과정

1. 시작 정점 결정

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

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

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

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

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

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

 

 

이미지 출처 : https://velog.io/@younge/Python-%EC%B5%9C%EB%8B%A8-%EA%B2%BD%EB%A1%9C-%EB%B2%A8%EB%A7%8C-%ED%8F%AC%EB%93%9CBellman-Ford-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

 

 

 

참고 : https://ssungkang.tistory.com/entry/Algorithm-%EB%B2%A8%EB%A7%8C%ED%8F%AC%EB%93%9CBellman-Ford-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

https://velog.io/@younge/Python-%EC%B5%9C%EB%8B%A8-%EA%B2%BD%EB%A1%9C-%EB%B2%A8%EB%A7%8C-%ED%8F%AC%EB%93%9CBellman-Ford-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98