4. Bellman-Ford(벨만 포드) : 최단 경로 탐색 - 2

Bellman Ford (벨만 포드)

최단 경로 탐색 - 2

 

오늘은 지난번 다익스트라에 이어 최단 경로를 탐색하는 알고리즘을 정리하려고 한다.

지난번 다익스트라 포스팅에서 다익스트라는 음의 사이클이 있는 그래프에서는 사용이 불가능하다고 하였다.

그 이유는 무엇일까?

 

우선, 다음과 같은 그래프의 시작 정점이 A라고 했을 때의 최단 경로를 구해보자.

 

[예상 결과]

A : 0

B : -4

C : 3

D : -7

E : 1

F : -3

 

[실제 결과]

 

시작 정점에서 이상한 값이 출력되는 것을 볼 수 있다.

---

다른 예시를 보자.

 

 

[예상 결과]

A : 0

B : 2 ( 재방문을 하지 않는다고 가정)

C : 5

D : 1

E : 3

 

[실제 결과]

 

역시, E 정점에서 이상한 값이 출력되는 것을 볼 수 있다.

 

이유가 뭘까?

 

이유는 다익스트라의 경우 방문한 정점과 연결된 정점들을 탐색하면서

최단 경로가 저장된 distance 변수와 가중치를 비교하여 가중치가 더 작은 경우

distance 변수를 갱신해주는 방식으로 구현되어있다.

 

이후 방문한 정점을 다시 방문하지 않도록 방문 처리해주는데

이 과정에서 음의 사이클에 존재하거나 음의 사이클을 거치는 경우

음의 사이클에 고립(?) 되어 비정상적인 값이 출력될 수 있다.

 

위에서 본 것처럼 가중치에 음의 값이 있는 경우 다익스트라 알고리즘은 비정상적으로 출력될 가능성이 있다.

이를 해결하기 위한 알고리즘이 오늘 설명할 벨만 포드 알고리즘이다.

 

벨만 포드 알고리즘은 가중치가 음의 값이 존재해도 정상적으로 최단 경로를 구할 수 있다.

뿐만 아니라  그래프 내의 음의 사이클을 탐지할 수 있다.

 

다익스트라와 갱신 방법은 똑같다.

다른 점은 탐색 방법인데 "최단 경로는 사이클을 포함할 수 없다." 라는 전제조건을 갖고 시작한다.

(Ex. 정점이 3개인 경우 간선은 2개가 존재.)

따라서 모든 정점을 (정점의 개수 - 1)번 반복을 통해 갱신한다. 

이후 한번 더 갱신을 진행하는데 이 과정에서 최단 경로가 갱신이 된다면 음의 사이클이 존재하는 경우라고 생각할 수 있다. 

 

위의 개념을 파이썬으로 구현해보았다.

 

위에서 언급한 그래프로 입력 값을 주면 이론상으로 구한 답과 동일 한 것을 볼 수 있다.

 

[Input]

6 9
A B C D E F
A B -4
A C 3
A E 3
A F 3
B D -3
B E 5
C F -1
D A -1
D F 4
A

 

[Output]

 

지금까지는 특정한 정점에서 다른 정점까지의 최단 경로를 탐색했다면

다음에는 모든 정점에서 모든 정점까지의 최단 경로를 탐색하는 플로이드 와샬 알고리즘을 설명하도록 하겠다.

 

충남대학교 컴퓨터공학과 이영석 교수님의 알고리즘 수업과 동빈나의 유튜브 강좌(https://youtu.be/611B-9zk2o4)를 참고했습니다.