다익스트라 알고리즘(Dijkstra Algorithm)

다익스트라 알고리즘은 음의 가중치가 없는 그래프에서, 한 vertex에서 모든 vertex들까지의(one-to-all) 최단거리를 구하는 알고리즘이다.

그럼 알고리즘의 내용을 살펴보자. 설명에서

• d[N]:  출발 vertex -> N 까지 계산된 최단거리
• S: 방문한 노드들의 집합
• Q: 방문하지 않은 노드들의 집합

를 의미한다.

아래와 같은 네트워크에서 A->F까지의 최단 거리 계산을 목표로 하는 상황이라고 가정하자.

1. 다익스트라 알고리즘은 아직 확인되지 않은 거리를 모두 무한(infinity)로 설정한다.

• 최단거리 update
  • 출발지로부터 출발지까지의 거리는 무조건 0이기 때문에 d[A] = 0으로 설정한다.
  • d[나머지 node]= infinity로 설정이되어있는데 실제로 무한이라는 의미는 아니고, 아직 확인되지 않았다는 의미이다.
• 다음 방문할 노드 결정
  • 위와 같이 d를 업데이트한 상황에서 제일 최단거리는 A이므로 A를 선택하여 방문한다. 그리고 방문하지 않은 노드들의 집합을 의미하는 Q에서 A를 제외시킨다.
  • 그리고 S에 A를 추가한다.

 

2. 루프를 돌려 이웃 노드를 방문하고 거리를 계산한다.

• 최단거리 update
  • 위의 step에서 A를 선택하여 방문하였으니, 이웃한 노드들까지의 거리를 계산하여, d[해당노드]가 새롭게 계산한 거리보다 크게 설정이 되어있을 경우 최단거리를 update해준다.
  • A에 이웃한 노드들은 B, C, D이며 해당 노드들까지의 거리는 각각 10, 30, 15이다. 기존에 해당 노드들까지의 최단거리가 모두 infinity로 설정이 되어있었으므로, d[B]=10, d[C]=30, d[D]=15로 update해준다.
• 다음 방문할 노드 결정
  • Q에 저장되어있는 노드들 중, d값이 가장 작은 노드를 선택해서 방문하게 되는데 현상황에선 B까지의 최단거리가 가장 낮으므로 B를 선택해서 방문한다. 그리고 Q에서 B를 제외시키게 된다.
  • 그리고 S에 B를 추가한다.

 

3. 위의 루프를 계속해서 반복

 

• 최단거리 update
  • 위의 step에서 B를 선택하여 방문하였으니, 이웃한 노드들까지의 거리를 계산하여 d를 update한다.
  • B에 이웃한 노드는 E밖에 없으므로 E까지의 최단거리를 계산한다. 이때 최단거리는 출발점을 기준으로 계산하므로 E까지 새롭게 계산된거리는 10(A->B) + 20(B->E) = 30이 되며, d[E]가 기존에 infinity로 설정이 되어있었으므로 d[E]=30으로 update한다.
• 다음 방문할 노드 결정
  • 그리고 마찬가지로 Q에 저장되어있는 노드들중에, d값이 가장 작은 노드를 선택해서 방문하게 되는데, 현 상황에서는 D까지의 최단 거리가 가장 낮으므로 D를 선택해서 방문한다. 그리고 Q에서 D를 제외시키게 된다.
  • 그리고 S에 D를 추가한다.

 

4. 더 빠른 경로를 발견한 경우

 

• 최단거리 update
  • 위의 step에서 D를 선택하여 방문하였으니, 이웃한 노드들까지의 거리를 계산하여 d를 update한다.
  • D에 이웃한 노드들은 C, F이다. 새롭게 계산된 C까지의 거리는 15(A->D)+5(D->C) = 20이고 새롭게 계산된 F까지의 거리는 15(A->D)+20(D->F) = 35이다.
  • 기존에 저장되어있는 d[C]=30인데 새롭게 계산된 거리가 더 빠르므로, d[C]=20으로 update해준다.
  • 마찬가지로 d[F]=infinity였으므로 d[F]=35로 update해준다.
• 다음 방문할 노드 결정
  • Q에 남아있는 노드들은 C, E, F이다. C, E, F중 d값이 가장 작은 노드는 C이다.
  • 따라서 C를 선택하여 방문하고 Q에서 C를 제외하게 된다.
  • 그리고 S에 C를 추가한다.

 

5. Q가 공집합이 된 이후

이러한 일련의 과정을 Q가 공집합이 될때까지 반복한다. 마지막 루프 이후,

• S = {A, B, D, C, F, E} (방문한 순서대로 정렬된 상태)
• d[A] = 0
• d[B] = 10
• d[C] = 20
• d[D] = 15
• d[E] = 30
• d[F] = 25
• Q = ∅

다음과 같이 세팅이 되어, F까지의 최단거리가 25임, A->B->C->F가 최단경로임을 알 수 있다.