그러면 이제 정점 1에 S에 있는 정점만 거쳐서 가는 방법이 하나 더 늘었네요. 바로 정점 4까지 거쳐서 가는 방법입니다. 이때 기존 경로 0->2로 갈 때 거리 distance[1]=30과 새롭게 나타난 경로 0->2->4로 갈 때 거리 distance[4]+weight(1, 4)=12+4=16을 비교해서 작은 값을 새로운 distance[1] 값으로 만듭니다. 이런 연산을 relax 연산이라고 하며, 이런 연산을 하는 것을 relaxation이라고 합니다.

이를 수식으로 만들어 볼까요?

합 S에 새롭게 삽입된 정점 v와 V-S에 속한 정점 u에 대해

distance[u] > distance[v] + weight(v, u)면,

distance[u] = distance[v] + weight(v, u)

이제 relaxation을 알았으니 데이크스트라 알고리즘을 그림으로 하나씩 진행해 보겠습니다.

다음 그림이 시작점입니다.

▲ 그림 14-4 데이크스트라 1