[ 알고리즘 개념 ] 벨만-포드 알고리즘 (Bellman-Ford Algorithm)

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

 

 

1. 개념

벨만 포드 알고리즘은 간선의 가중치가 음의 값인 경우도 동작하는 최단 경로 알고리즘이다.

다익스트라 알고리즘과 마찬가지로 시작 정점에서 다른 모든 정점으로의 최단 경로를 구하는 점에서 유사하다.

하지만 다익스트라 알고리즘은 0보다 작은 '음의 간선' 이 있으면 정상적으로 동작하지 않는다는 점에서 다르다.

 

하지만 벨만 포드는 시간복잡도가 O(VE) 이므로 다익스트라의  O(ElogV) 보다 비효율적이다. 따라서, 다익스트라를 사용할 수 있는 경우라면 그쪽을 사용하는 편이 효율성의 측면에서 더 낫다.

 

벨만 포드 알고리즘에서 '음의 간선' 이 있는 경우는 동작하지만,  '음의 사이클' 이 존재하는 경우에는 동작하지 않는다는 점을 유의해야 한다. 만약 음의 사이클을 만나면 계속 최단 경로의 값이 줄어들면서 테이블을 무한정 갱신하게 되는 현상이 발생한다.

 

다음은 다익스트라 알고리즘에 관한 게시글이다.

codingexplore.tistory.com/51

[ 알고리즘 개념 ] 다익스트라 알고리즘 (Dijkstra Algorithm)

 

2. 동작 과정

벨만 포드 알고리즘은 "간선을 최대 1개 사용하는 최단경로" , "간선을 최대 2개..." … 방식으로 간선을 최대 n-1 개 사용하는 최단경로까지 구한다.

 

1) 최단 거리 테이블 초기화

2) 모든 간선을 한번 씩 돌면서 최단거리 테이블 갱신

3) 2번 과정을 1 ~ V-1  반복

 

3. 동작 예

#V0 : 최단거리 테이블 초기화 - 출발 노드는 0으로, 나머지는 INF(무한) 로 초기화

---

#V1, V2 : 간선 1개를 사용할 경우, 간선 2개를 사용할 경우 

 

: 간선을 1개 사용할 경우 갱신

 A -> B = -1

 A -> C = 4

 

: 간선을 2개 사용할 경우 갱신

A -> B-> C = 2

A -> B -> E = 1

---

#V3, V4 : 간선 3개를 사용할 경우, 간선 4개를 사용할 경우 

 

 

: 간선을 3개 사용할 경우 갱신

A -> B -> E -> D = -2

 

: 간선을 4개 사용할 경우 갱신

 X

 

 

관련글

다음은 벨만-포드 알고리즘을 파이썬으로 어떻게 구현할 것인가에 대해 정리한 게시글이다.

구체적인 소스를 짜기가 어려울 때 참고하면 좋다.

codingexplore.tistory.com/58

[ 알고리즘 개념 ] 벨만-포드 알고리즘 (Bellman-Ford Algorithm) 구현 - 파이썬(Python)

---

참고자료

www.geeksforgeeks.org/bellman-ford-algorithm-dp-23/

Bellman–Ford Algorithm | DP-23 - GeeksforGeeks