목적
가중치가 존재하는 그래프에 대하여, 두 지점 사이의 최단거리를 구한다.
기본 생각
너비 우선 탐색과 탐욕법을 이용한다. 최단거리를 찾기 위해 어떤 노드를 방문했을때, 인접한 노드들을 대기열에 넣는다. 이때, 탐욕법을 이용하여, 가장 작은 가중치를 가진 인접노드를 넣는다.
=> 우선하여 넣는 것인지 그것만 넣는 것인지는 확인이 필요하다.
개념 익히기
참고 - Data structures and Algorithms in Java 6 ed
key words
- cloud
- u
- D(v)
너비 우선 탐색은 시작노드에서 출발하여, 인접 노드들을 방문할 대기열에 넣는 방식으로 이루어진다. 이때, 방문한 영역이 시작점부터 둥글게 퍼져나가므로, 그 모양을 cloud 로 비유가 가능하다. 이 때, cloud 안의 어떤 노드 v 에 대해서 D(v) 를 현재까지의 탐색된 최단경로라고 정의 할 수 있다.
이때, u 는 cloud 바깥에서 최소의 가중치를 갖는 녀석으로 고른다.
Edge relaxation
u 가 cloud 로 포함되면, D(v) 를 업데이트 해주어야 한다. 새롭게 포함된 u 를 경유하는 경로가 기존 경로 보다 작다면 D(v) 를 새로운 값으로 바꾸어 준다.
if D(u) + w(u, v) < D(v):
D(v) = D(u) + w(u, v)