회원가입

[그래프] 30. 엣지 Relaxation

NULL 2021-09-28

Dijkstra 알고리즘에서는 Node를 하나씩 방문한다.

Node들을 방문하면서 해당 Nodedistance predecessor 변수들을 업데이트 해준다.

이것을 relaxation 동사로는 relax 라고 한다.

 

좀 더 정확히는 A 에서 B 를 방문할 때, B 의 변수를 업데이트해주는 것을

"엣지 (A, B)relax 한다."

라고 표현한다.

 

아래 그래프를 보자, Node AB 가 있다.

Adistance 는 3

Bdistance 는 7

엣지 (A, B) 는 가중치가 2

 

엣지 (A, B)relax 한다는 건 여러 단계가 있다.

먼저 Adistance엣지 (A, B) 가중치를 더한 후, Bdistance 와 비교를 한다.

Adistance엣지 의 가중치를 더한 5는 Bdistance 7 보다 작다.

 

Bdistance 가 7이라는 건 지금 현재까지 아는 정보로 시작점에서 B 까지 최단 거리는 7이라는 뜻이다.

Adistance엣지 의 가중치를 더한 값이 5라는 것은 현재까지 아는 A 의 최단 거리는 3 이고, A 에서 B 까지 가는 경로는 거리가 2라는 말이다.

이걸 합치면 5이다.

시작점에서 B 까지의 경로 중 7보다 더 짧은 거리를 발견한 것이다.

이때, Bdistance 를 5로 바꿔준다.

지금까지 본 결과 B 까지의 최단 거리는 5라고 바꿔주는 것이다.

그리고 마지막 하나를 더하면 되는데, BpredecessorA 로 바꿔준다.

 

반대로 이런 경우도 생각해보자.

Adistance 가 3

Bdistance 가 7

엣지 (A, B) 는 가중치가 6

 

이번에도 Adistance엣지의 가중치를 더한다. 9 이다.

그리고 이것을 Bdistance 7과 비교한다.

9가 더 크다.

이때는 아무것도 안 해주면 된다.

지금까지 찾은 B까지의 최단 거리가 7인데, 새로 찾은 거리 9는 이것보다 크니까 바꿀 필요가 없는 것이다.

이렇게 A 에서 B 로가는 경로distance 가 현재 Bdistance 보다 작은지 확이하고 업데이트해주는 걸 엣지 (A, B) relax 라고 한다.

 

최단 거리 예산 값을 계속 줄여 나가는 게 Node 의 긴장을 풀어준다는 개념과 비슷하기 때문에 사용하는 용어이다.

0 0