지난 글 : [알고리즘] - 깊이 우선 탐색
벨먼-포드(Bellman-Ford) 알고리즘은 그래프의 최단 경로 문제를 해결하기 위한 알고리즘이다. 최단 경로 문제에서는 간선에 가중치가 부여된 '가중 그래프'가 주어지며 시작점과 종점이 지정된다. 시작점부터 종점까지의 경로 중 간선의 가중치 합이 가장 작은 것을 구하는 문제다.
1
B---1---E
/|\ /|\
9 | 3 5 | 7
/ | \ / | \
"A" 6 D 3 G
\ | / \ | /
2 | 2 6 | 4
\|/ \|/
C---9---F여기서 A를 시작점, G를 종점으로 한다. 각 종점의 초기 가중치를 설정한다. 시작점은 0, 그 외의 정점은 무한대로 설정한다. 이 가중치는 A부터 해당 정점까지의 최단 경로의 길이를 나타내는 임시 가중치다. 계산이 진행됨에 따라 이 값이 점점 작아지며 올바른 값으로 수렴하게 된다.
2
'B'--1---E
/|\ /|\
9 | 3 5 | 7
/ | \ / | \
"A" 6 D 3 G
\ | / \ | /
2 | 2 6 | 4
\|/ \|/
C---9---F모든 간선 중 하나를 선택한다. 여기서는 A-B를 연결하는 간선을 선택한다. 선택한 간선의 한쪽 정점에서 다른 정점으로 이동하기 위한 가중치를 계산한다. 계산 방법은 '시작 정점의 가중치 + 간선의 가중치'다. 계산은 한 방향씩 하지만 어느 쪽을 먼저 계산할지는 상관없다. 여기서는 가중치가 작은 정점에서 큰 정점으로 가는 방향을 먼저 계산한다.
3
'B'--1---E
/|\ /|\
9 | 3 5 | 7
/ | \ / | \
"A" 6 D 3 G
\ | / \ | /
2 | 2 6 | 4
\|/ \|/
C---9---F정점 B보다 정점 A가 현재 가중치가 작으니 정점 A에서 정점 B로 가는 경우를 먼저 계산한다. 정점 A의 가중치는 0, 간선의 가중치가 9이므로 9가 된다.
4
'B'--1---E
/|\ /|\
9 | 3 5 | 7
/ | \ / | \
"A" 6 D 3 G
\ | / \ | /
2 | 2 6 | 4
\|/ \|/
C---9---F계산한 결과가 현재 값보다 작으면 가중치를 새로운 값으로 변경한다. 정점 B의 현재 가중치는 무한대이므로 9가 작다. 따라서 가중치를 9로 변경한다. 책에서는 값이 변경된 경우 어느 정점에서 온 것인지 표시한다. 반대 방향인 B에서 A로 향하는 경우 정점 B의 가중치가 9이므로 정점 B에서 A로 가는 가중치는 9 + 9 = 18이 된다. A의 현재 가중치 0과 비교하면 현재 값이 작으므로 가중치를 변경하지 않는다.
5
B---1---E
/|\ /|\
9 | 3 5 | 7
/ | \ / | \
A 6 D 3 G
\ | / \ | /
2 | 2 6 | 4
\|/ \|/
C---9---F같은 작없을 모든 간선에 적용한다. 모든 간선에 대한 변경 작업이 완료되면 1 라운드 종료, 같은 작업을 가중치가 변경되지 않을 때까지 반복한다.
6
B---1---E
/|\ /|\
9 | 3 5 | 7
/ | \ / | \
A 6 D 3 G
\ | / \ | /
2 | 2 6 | 4
\|/ \|/
C---9---F2 라운드 작업이 끝났다. 정점 B와 정점 E의 가중치가 변경되었으므로 한 라운드 더 작업한다.
7
B---1---E
/|\ /|\
9 | 3 5 | 7
/ | \ / | \
A 6 D 3 G
\ | / \ | /
2 | 2 6 | 4
\|/ \|/
C---9---F3 라운드 변경 작업을 했지만 정점의 가중치가 변경되지 않았으므로 작업을 멈춘다. 이 시점에서 알고리즘에 의한 탐색이 완료되며, 시작점에서 모든 정점까지의 최단 경로가 나온다. 위 탐색에 의해 시작점 A에서 종점 G로 가는 최단 경로는 A-C-D-F-G로 가중치의 합이 제일 작다.
참고 서적 :
