벨만-포드 알고리즘(Bellman-Ford algorithm)은 가중 유향 그래프에서 최단 경로 문제를 푸는 알고리즘이다. 이때 간선의 가중치는 음수일 수도 있다. 데이크스트라 알고리즘은 벨만-포드 알고리즘과 동일한 작업을 수행하고 실행속도도 더 빠르다. 하지만 데이크스트라 알고리즘은 가중치가 음수인 경우는 처리할 수 없으므로, 이런 경우에는 벨만-포드 알고리즘을 사용한다.

V와 E가 각각 그래프에서 꼭지점과 모서리의 개수라고 한다면, 벨만-포드 알고리즘의 실행시간은 O(VE)이다.





----지식인 내용----

벨만 포드 알고리즘 ( 간선의 가중치가 음의 가중치를 가져도 상관 없음)

벨만 포드 알고리즘은 간선을 최대 1개 사용하는 최단경로...

간선을 최대 2개 사용하는 최단 경로...

간선을 최대 3개 사용하는 최단 경로...

....

간선을 최대 n-1 개 사용하는 최단 경로까지 구해나가는 것으로 결과값을 찾아냅니다.

 

- 1 : 시작 정점 r의 최단 거리만 0으로 셋팅 하고 나머지 정점이 갖는 값을 모두 무한대 값으로 초기화시킵니다.

- 2 : 모든 간선을 한번씩 살피면서 해당 간선으로 인해 앞에서 설정한 최단 거리가 더 짧아질 수 있는 지 봅니다.

 

예를 들어  처음은 r 에서 나갈수 있는 모든 간선들을 확인 하여 가장 작은 값으로 갈수 있는 정점을 선택합니다. ( i = 1 ) 간선 1개 사용

이번에는 한개의 간선에 대해서 확장되어지느 그 위치에서 또 나갈수 있는 모든 간선에 대해 값을 계산 합니다. ( 간선 2개 사용)

이를 반복하는데 이미 정점이 다른 간선이 지나가면서 값이 설정되어 있을 경우

막금 들어온 간선의 최종 값과 비교하여 작은 값을 저장 합니다.

 

위를 n -1 만큼 반복합니다.( n은 정점의 수)

 

벨만 포드 알고리즘은 다익스트라 알고리즘에서 사용하지 못하는 음의 가중치를 갖는 그래프에 대해서 해결을 해주지만

다익스트라 알고리즘의 O(ElogV)시간 복잡도에 비해 O(EV)라는 시간 복잡도를 갖음으로써 수행시간이 느리다는 약점을 가지고 있습니다.



 

 



http://ko.wikipedia.org/wiki/%EB%B2%A8%EB%A7%8C-%ED%8F%AC%EB%93%9C_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

'기타' 카테고리의 다른 글

풀업저항  (0) 2011.10.21
래치 [ latch ]  (0) 2011.10.20
fetch  (0) 2011.10.20
DNS(Domain Name System)란?  (0) 2011.09.28
데이크스트라 알고리즘  (0) 2011.09.24
벨만-포드 알고리즘  (0) 2011.09.24
by 김생 2011.09.24 17:52