다익스트라 알고리즘

다익스트라 알고리즘(Dijkstra algorithm)은 그래프에서 노드 사이의 최단 경로를 찾는 알고리즘이다.

1. 개요

 - 음의 가중치가 없는 그래프에서 한 노드에서 다른 모든 노드까지의 최단거리를 구하는 알고리즘이다.

 - 방향그래프, 무방향 그래프 모두 상관없다.

 - 에츠허르 다익스트라가 고안한 알고리즘으로, 그가 처음 고안한 알고리즘은 O(V²)의 시간복잡도를 가졌다.

   이후 우선순위 큐(=힙 트리)등을 이용한 더욱 개선된 알고르짐이 나오며, O(ElogV)의 시간복잡도를 가지게 되었다.

   O(ElogV)의 시간복잡도를 가지는 이유는 힙에 최악의 경우 E번의 탐색 노드를 집어넣는 경우가 발생하게 되는데,

   이러한 경우에 O(ElogV)의 시간복잡도가 나오며, 중복 간선을 허용하지 않는 그래프라면 O(E) <= O(V²) 이므로 O(logE) <= O(logV²)와 같다.

   이때 O(logV²) = O(2 x logV) 이므로, 상수를 제거하면 O(ElogV)가 된다.

   물론 여기서 탐색에 소요되는 시간 O(V + E)는 O(ElogV)보다 작으므로 무시한다.

 - 최단경로를 구하는 다른 알고리즘인 플로이드-워셜 알고리즘은 가능한 모든 노드쌍들에 대한 최단거리를 구하는 알고리즘인 반면,

   다익스트라 알고리즘으로는 하나의 노드에서부터의 최단경로로 밖에 구할 수 없다.

   다만 시간은 플로이드 알고리즘이 더 오래걸리므로, 문제 상황에 따라 그때 그때 적합한 알고리즘을 사용하도록 하자.

2. 알고르짐의 실질적 이용

 - 가능한 적은 비용으로 가장 빠르게 해답에 도달하는 경로를 찾아내는 대부분의 문제에 응용된다.

   고로 실질적 이용 예가 얼마나 많은지에 대해 더 이상의 자세한 설명은 생략하낟.

 - 예를 들어 루빅스 큐브를 푸는 프로그램을 다익스트라 알고리즘으로 만들 수 있고, 내비게이션에서 지도를 각 도시들을 노드로,

   도로들을 간선으로 갖는 그래프로 간주한다면, 두 도시를 잇는 가장 빠른 길을 찾는 문제로 볼 수 있다.

   미로탐색 알고리즘으로 사용 할 수 있다.

   라우팀에서도 OSPF 방식의 프로토콜의 경우가 좋은 예가 될 수 있다.

3. 그림 설명(문제가 있을까봐... 그림 다 뺌) -> 단계별 설명 입니다.

 - 예를 들어, 다음과 같은 네트워크가 존재한다고 가정하자.

   먼저, A 라우터의 목표는 F까지의 최단 거리 계산이며, 수단으로는 다익스트라 알고리즘을 활용한다. 

   이때, 각 데이터의 의미는 다음과 같다.

     ㉠ S = 방문한 노드들의 집합입니다.

     ㉡ d[N] = A -> N 까지 계산된 최단 거리입니다.

     ㉢ Q = 방문하지 않은 노드들의 집합입니다.

A,B,C,D,E,F의 거리 구조... → 이동가능함을 말합니다.

 + A → B : 10

 + A → C : 30

 + A → D : 15

 + B → E : 20

 + C → F : 5

 + D → C : 5

 + D → F : 20

 + E → F : 20

 + F → D : 20

 ⓐ 다익스트라 알고리즘은 아직 확인되지 않은 거리는 전부 초기값을 무한으로 잡는다.

     S = {}

     d[A] = 0

     d[B] = infinity

     d[C] = infinity

     d[D] = infinity

     d[E] = infinity

     d[F] = infinity

     Q = {A, B, C, D, E, F}

     

    ㉠ 출발지를 A로 초기화했기 때문에, 출발지와 출발지의 거리는 방문할 필요도 없이 당연히 0 값을 가진다.

        즉, d[A]=0 이 된다. (A노드를 방문한 것은 아니다.)

    ㉡ 출발지를 제외한 모든 노드들도 아직 방문하지 않았기에, d[다른 노드]=무한이 된다.

    ㉢ Q는 방문하지 않은 노드들의 집합이므로, 초기화할 때는 모든 노드들의 집합이 된다.

    ㉣ S는 공집합 상태이다.

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

     S = {A}

     d[A] = 0

     d[B] = 10

     d[C] = 30

     d[D] = 15

     d[E] = infinity

     d[F] = infinity

     Q = {B, C, D, E, F}   

  

    ㉠ 루프의 시작은 거리가 최소인 노드(d[N]이 최소값인 노드 N)를 Q(방문하지 않은 노드의 집합)에서 제거하고, 

        그 노드를 S(방문한 노드의 집합 및 최소 경로)에 추가한다. 즉, N을 '방문한다'는 의미이다.

    ㉡ 이후, 모든 이웃 노드와의 거리를 측정하여 d[N](=출발지로부터 N까지 계산된 최소 거리값) + (N과 이웃 노드 간의 거리값) = (출발지부터 이웃노드까지의 거리값)이 계산된다.

    ㉢ 다만, 지금은 첫 번째 루프만을 끝낸 상태이므로, 단순히 0 + (이웃 노드와 출발지 사이의 거리값) = (출발지와 이웃 노드 간의 거리값)이 각 이웃 노드에 기록된다. 따라서, d[B] = 10, d[C] = 30, d[D] = 15로 값을 변경한다.

  ⓒ 첫 루프 이후의 그래프의 상태가 업데이트되는 방식입니다.

     S = {A, B}

     d[A] = 0

     d[B] = 10

     d[C] = 30

     d[D] = 15

     d[E] = 30

     d[F] = infinity

     Q = {C, D, E, F}   

   - 이제 루프가 반복적으로 작동하는 방법을 설명한다. 밑의 그림들 또한 루프 안에서 알고리즘이 진행되는 순간들을 반복 설명한다.

    ㉠ 이전에 설명했듯이, 방문할 노드는 Q에 남아있는 노드들 중 d[N] 값이 제일 작은 것으로 선택된다.

        따라서, Q{B, C, D, E, F} 중 B가 d[B] = 10 으로 제일 작은 값을 가지므로, B를 방문하여 S에 추가하고 Q에서 제거한다.

    ㉡ 이제, B의 이웃 노드들을 모두 탐색하여 거리를 재고 d[N]에 기록한다.

        B의 이웃 노드는 E 뿐이므로, d[E]값이 무한에서 d[B]+(B와 E 사이의 값 = 20)=30 으로 업데이트된다.

        여기서 d[B] 값을 추가하는 이유는 출발지부터의 거리값을 재기 위해서다.

  ⓓ 더 빠른 경로를 발견한 경우 입니다.

     S = {A, B, D}

     d[A] = 0

     d[B] = 10

     d[C] = 20 <- 값이 업데이트됩니다.

     d[D] = 15

     d[E] = 30

     d[F] = 35

     Q = {C, E, F}

      ㉠ 3번째 그림에서 설명했듯이, 이번에 선택 방문되는 노드는 D이다.

          Q의 원소 중에서 제일 낮은 d[N] 값을 가지고 있기 때문이다.

          그래서, S에 D가 추가되어 있다.

      ㉡ 이제 D의 이웃 노드들(C, F)의 거리를 잰 후, d[N]값을 업데이트한다. 

          특별한 상황은 d[C]의 값이 A를 방문할 때 이미 계산되어 30으로 정해져 있었으나,

          D를 방문하여 C와의 거리를 확인해보니 20으로 더 짧은 최단 경로가 발견되었다! 그러므로,d[C]의 값을 30에서 20으로 변경한다.

      ㉢ d[F]의 경우는 원래의 값이 무한이므로, 더 작은 값인 15+20=35 로 변경한다.

   ⓔ 또 다른 반복 루프 상황입니다.

     S = {A, B, D, C}

     d[A] = 0

     d[B] = 10

     d[C] = 20 

     d[D] = 15

     d[E] = 30

     d[F] = 25 <- 값이 업데이트됩니다.

     Q = {E, F}

      ㉠ Q{C, E, F}에서 d[C] = 20 으로 C를 방문하여, S는 {A, B, D, C}가 되었다.

      ㉡ 다시 이웃 노드와의 거리 계산을 해보니, 이번에는 (A→D)+(D→F)=15+20=35보다, (A→D)+(D→C)+(C→F)=15+5+5=25로 더 작은 값을 가지는 것이 발견되었다.

          d[F]=25 로 업데이트한다. 

 - 이 일련의 과정이 반복되어 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 = 0

   * 목적지가 F였으므로, A→D→C→F가 최단 경로이며, 거리는 25로 결정된다.

4. 알고리즘

 - 다익스트라 알고리즘은 다음과 같다. P[A][B]는 A와 B 사이의 거리라고 하자. 

    ㉠ 출발점으로부터의 최단거리를 저장할 배열 d[v]를 만들고, 출발 노드에서 0을, 출발점을 제외한 다른 노드들에는 매우 큰 값 INF를 채워 넣는다.

        보통은 최산거리 저장 배열의 이론상 최대값에 맞게 INF를 정한다.

        실무에서는 보통 d의 원소 타입에 대한 최대값으로 설정하는 편.

    ㉡ 현재 노드 A 에 출발 노드를 저장한다.

    ㉢ A로부터 갈 수 있는 임의의 노드 B에 대해, d[A]+P[A][B]와 d[B]의 값을 비교한다.

    ㉣ 만약 d[A]+P[A][B]가 더 짧다면, d[B]의 값을 이 값으로 갱신시킨다.

    ㉤ 모든 이웃 노드 B에 대해 이 작업을 수행한다.

    ㉥ A의 상태를 "방문 완료"로 바꾼다. 그러면 이제 더 이상 A는 사용하지 않는다.

    ㉦ "미방문"상태인 모든 노드들 중, 출발점으로부터의 거리가 제일 짧은 노드 하나를 골라서 그 노드를 A에 저장한다.

    ㉧ 도착 노드가 "방문 완료"상태가 되거나, 혹은 더 이상 미방문 상태의 노드를 선택할 수 없을 때까지, 3~7의 과정을 반복한다.

 - 이 작업을 마친 뒤, 도착 노드에 저장된 값이 바로 A로부터의 최단 거리이다. 만약 이 값이 INF라면, 중간에 길이 끊긴 것임을 의미한다.

 - ㉦ 단계에서, 거리가 가장 짧은 노드를 고르는 것은 공짜가 아니다.

   모든 노드를 순회해야 하므로 시간복잡도에 결정적인 영향을 미치게 되는데, 이때 제대로 구현된 우선순위 큐를 활용한다면 이 비용을 줄일 수 있다.

   최단거리를 갱신할 때 우선순위 큐에도 <위치, 거리>의 쌍을 넣어주고, 거리가 가장 짧은 노드를 우선순위 큐를 이용해 고르면 된다.

   이 비용은 삽입에 최대 O(lgN) 출력에 O(lgN)이므로, 모든 노드 순회(O(N))보다 저렴하다.