×
Crocus
공부한 내용을 정리하는 블로그로 시작한
Crocus는 2014년 1월 14일 부터 시작하여
현재 월 6만명, 총 2,877,130명의 방문자 수를 기록하고 있습니다.
Donation
이제 많은 사용자들이 이용하는 만큼
더 다양한 서비스 개발/제공을 위해 후원금을 모금하고자 합니다.
후원을 해주시는 분들은 Donators 명단에 성명, 후원금을 기입해드리며
Crocus 블로그가 아닌 다른 곳에 정리해둔 저만의 내용을 공유해 드리고자 합니다.
Account
예금주 : 고관우
신한은행 : 110-334-866541
카카오뱅크 : 3333-01-7888060

👉 후원 페이지 바로가기 Donators
익명 : 5000원(Crocus응원합니다.)
busyhuman: 5000원(유용한 지식 감사합니다.)
익명 : 5000원(알고리즘 학습러)
반응형

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


그래프 상에 존재하는 두 노드 간의 최단 거리를 구하고 싶을 때 이용할 수 있다.

그래프 공부 시, 아주 중요한 알고리즘이며, 

이 알고리즘 및 다익스트라 알고리즘(Dijkstra Algorithm) 그리고 

플로이드 와샬 알고리즘(Floyd-Warshall Algorithm) 이 3가지 알고리즘을 통해 최단 경로를 구할 수 있다.


이러한 세가지 알고리즘은 각각 정점과 간선의 개수가 어떻게 구성되냐에 따라 시간 복잡도의 차이가 있기에,


각 상황에 맞는 알고리즘을 이용하면 된다.


이번 게시물에서는 벨만 포드에 대해 알아 보도록 한다.



벨만 포드 알고리즘은, 다익스트라에서 할 수 없었던 음의 가중치도 계산 할 수 있도록 한 방식이지만


다익스트라보다 시간 복잡도가 높기에(더 느리기에) 어떤 상황에서 이용해야 할 지 잘 생각하여 써야한다.



우선 벨만 포드 알고리즘에 대한 전제 조건은 다음과 같다.


1. 최단 경로는 사이클을 포함할 수 없기 때문에, 최대 |V|-1개의 간선만 사용할 수 있다.

즉, 3개의 노드가 있을 때, 2개까지 간선만 허용한다는 의미이다.

2. 최단 거리가 업데이트 되는 노드가 없어질 때 까지 계속해서 반복하여 구해주고, 음의 가중치로 인해 업데이트를 무한히 하게 되는 경우 탈출 시켜주어야 한다.(무한히 반복할 때는 최단거리가 없다고 한다.) 



다음은 벨만 포드 알고리즘의 시간 복잡도 공간 복잡도 분석이다.








벨만 포드는 그림을 통해 확인해 보는것이 글보다 더 쉽다.




다음과 같이 방향이 존재하는 정점 5개, 간선 9개의 그래프가 주어져있고, 0에서 2로 가는 최단 거리를 구해보자.


벨만 포드 알고리즘을 통해 최단 거리를 구하는 방식은 

계속해서 모든 간선을 이용하여 a정점에서 b정점으로 갈 때, 거리가 짧아지는 경우가 생긴다면 계속 업데이트를 해주는 방식이다.

V(정점)*E(간선)번 반복후 종료 된다.



 << 첫번째 itreation(반복) >> 



처음에는 모든 정점에 대해 최단 거리를 무한대로 설정한다. 


그리고 0번 정점에서 2번 정점의 최단거리를 구하니 0번 정점에 대해서는 최단 거리를 0으로 설정한다.


첫번째로 0에서 1로가는 간선이 없으니 0에서 2로 가는 간선을 보자.


가중치가 1이므로 2번 정점에 대한 최단 거리를 1로 업데이트 해준다.(1이 무한대 보다 최단거리니)



그리고 3번 노드를 확인하고 최단 거리를 5로 업데이트 해준다.



0번 정점 -> 1,2,3,4번 정점에 대한 모든 확인이 끝났으니 1번 정점으로 간다.


1번 정점 -> 2번 정점은 (무한대 - 2) > 1(현재 2번 정점의 최단거리)이므로 업데이트 하지 않는다.



1번 정점에 대한 확인이 끝났으니, 2번 정점으로 간다.


2번 정점 -> 1번 정점은 간선의 가중치가 4이니, 2번까지의 최단 거리 합(1) + 가중치(4) = 5를 1번 노드에 업데이트한다.



2 -> 3 :: 1 + 4 = 5를 업데이트해준다.



2번에 대해서도 끝이 났으니 3번 정점으로 이동한다.


3 -> 0 :: 5-1 = 4이지만, 0번에는 이미 0이 저장되어 있기에 4 > 0 이므로 업데이트 하지 않는다.



3 -> 1 :: 5 + 3 > 5 이기에 업데이트 하지 않는다.



3번에 대해서도 끝이 났으니 4번을 확인한다.


4 -> 0 :: 무한대 + 1 > 0 , 따라서 업데이트 하지 않는다.



4 -> 2 :: 무한대 - 1 > 1 , 따라서 업데이트 하지 않는다.


이렇게 첫번째로 첫번째 itreation을 끝냈다.



 << 두번째 itreation(반복) >> 



0에서 1로 갈 때 업데이트 할 것이 없으므로 하지 않는다.



0 -> 3 :: 업데이트 하지 않는다.



1 -> 2 :: 업데이트 하지 않는다.



2 -> 1 :: 업데이트 하지 않는다.



2 -> 3 :: 업데이트 하지 않는다.



3 -> 0 :: 업데이트 하지 않는다.



3 -> 1 :: 업데이트 하지 않는다.



4 -> 0 :: 업데이트 하지 않는다.



4 -> 2 :: 업데이트 하지 않는다.


결국 아무것도 업데이트 하지 않았고, 3,4,5번째 반복에서도 업데이트가 되지 않는다.


하지만 계속 반복한다는 점은 알고 있어야한다.



실제 벨만 포드 알고리즘이 추적한 경로는 다음과 같다.




결국 0에서 N의 최단 거리는 다음과 같다.

0 -> 0 :: 0

0 -> 1 :: 5

0 -> 2 :: 1

0 -> 3 :: 5

0 -> 4 :: INF(0에서 4로 가는 길이 없으므로 초기화 한 무한대가 된다.)


따라서 0에서 2까지의 최단 거리는 1이다.


이렇게 구하는 알고리즘을 벨만 포드 알고리즘(Bellman-Ford Algorithm)이라고 한다.


소스 코드는 다음 게시물에 올릴 예정이다.




반응형