지난 글 : [알고리즘] - 벨먼-포드 알고리즘
다익스트라(Dijkstra) 알고리즘은 지난 글에서 배운 벨먼-포드 알고리즘과 같이 그래프의 최단 경로 문제를 해결하기 위한 알고리즘이다. 시작점부터 종점까지의 경로 중 가중치의 합이 가장 작은 것을 구한다.
1
B---3---E
/|\ / \
2 | 1 4 9
/ | \ / \
A 6 D G
\ | /
5 | 7
\| /
C---8---F시작점 A, 종점 G이다. 먼저 각 정점의 초기 가중치를 시작점은 0, 그 외 정점은 무한대로 설정한다.
2
'B'--3---E
/|\ / \
2 | 1 4 9
/ | \ / \
"A" 6 D G
\ | /
5 | 7
\| /
'C'--8---F현재 정점을 " "로, 후보 정점은 ' '로 표시한다. 현재 정점에서 갈 수 있는, 탐색하지 않은 정점을 찾고 후보로 설정한다.
3
'B'--3---E
/|\ / \
2 | 1 4 9
/ | \ / \
"A" 6 D G
\ | /
5 | 7
\| /
'C'--8---F후보인 각 정점의 가중치를 계산한다. 계산 방법은 '현재 있는 정점의 가중치 + 현재 있는 정점에서 후보 정점까지 가는 가중치'다. 계산한 결과가 정점의 현재 가중치보다 작으면 가중치를 새로운 값으로 변경한다. 정점 B,C의 현재 가중치는 무한대로 계산한 결과가 작다. 따라서 각각 새로운 값으로 변경한다.
4
'B'--3---E
/|\ / \
2 | 1 4 9
/ | \ / \
"A" 6 D G
\ | /
5 | 7
\| /
'C'--8---F후보 정점 중에서 가중치가 가장 작은 정점을 선택한다. 여기서는 B가 선택된다. 이 시점에서 선택한 정점 B로 가는 경로 A-B는 시작점에서 정점 B로 가는 최단 경로로 정해진다. 이유는, 다른 경로를 사용하면 반드시 정점 C를 경유해야 해서 결과적으로 현재 경로보다 가중치가 높아지기 때문이다.
5
"B"--3--'E'
/|\ / \
2 | 1 4 9
/ | \ / \
A 6 'D' G
\ | /
5 | 7
\| /
'C'--8---F최단 경로를 결정한 정점 B로 이동한다. 현재 있는 정점에서 갈 수 있는 정점을 새로운 후보로 추가한다. 위의 계산 방법과 같은 방법으로 각 후보 정점들의 가중치를 계산한다. 후보 정점 중 가중치가 가장 작은 정점을 선택한다. 여기서는 D가 선택된다. 정점 D로 가는 경로 A-B-D가 시작점에서 정점 D로 가는 최단 경로로 결정된다.
6
B---3--'E'
/|\ / \
2 | 1 4 9
/ | \ / \
A 6 "D" G
\ | /
5 | 7
\| /
'C'--8---F경로 A-B-D는 후보 정점 중 가장 가중치가 작은 것을 선택한 결과다. 따라서 다른 정점을 경유해 D로 가면 가중치가 반드시 지금보다 높아지게 된다. 같은 작업을 종점 G에 도착할 때까지 반복한다. 현재 후보는 C와 E고 둘 다 같은 값(5)을 가지므로 어느 쪽을 선택하든 상관없다.
7
B---3--'E'
/|\ / \
2 | 1 4 9
/ | \ / \
A 6 D G
\ | /
5 | 7
\| /
"C"--8--'F'C로 이동한다. 결과적으로 C로 가는 최단 경로가 결정된다. 새로운 후보 F가 추가된다.작은 쪽인 E를 선택하고 E로 가는 최단 경로를 결정한다.
8
B---3--"E"
/|\ / \
2 | 1 4 9
/ | \ / \
A 6 D 'G'
\ | /
5 | 7
\| /
C---8--'F'E로 이동했다. G가 새로운 후보가 되고 G의 가중치가 변경된다. 후보 F와 후보 G 중 가중치가 더 작은 F를 선택해 F로 가는 최단 경로를 결정한다.
9
B---3---E
/|\ / \
2 | 1 4 9
/ | \ / \
A 6 D 'G'
\ | /
5 | 7
\| /
C---8--"F"F로 이동한다. 후보는 G 밖에 없으므로 G를 선택하면 G로 가는 최단 경로가 결정된다.
10
B---3---E
/|\ / \
2 | 1 4 9
/ | \ / \
A 6 D "G"
\ | /
5 | 7
\| /
C---8---F시작점 A부터 종점 G까지 가는 최단 경로는 A-B-E-G다.
참고 서적 :
