다익스트라 알고리즘

1. 개요

2. 알고리즘의 실질적 이용

3. 알고리즘

1. 출발점으로부터의 최단거리를 저장할 배열 d[v]를 만들고, 출발 노드에는 0을, 출발점을 제외한 다른 노드들에는 매우 큰 값 INF를 채워 넣는다. (정말 무한이 아닌, 무한으로 간주될 수 있는 값을 의미한다.) 보통은 최단거리 저장 배열의 이론상 최대값에 맞게 INF를 정한다. 실무에서는 보통 d의 원소 타입에 대한 최대값으로 설정하는 편.[2][3]
2. 현재 노드를 나타내는 변수 A에 출발 노드의 번호를 저장한다.
3. A로부터 갈 수 있는 임의의 노드 B에 대해, d[A] + P[A][B][4]와 d[B][5]의 값을 비교한다. INF와 비교할 경우 무조건 전자가 작다.
4. 만약 d[A] + P[A][B]의 값이 더 작다면, 즉 더 짧은 경로라면, d[B]의 값을 이 값으로 갱신시킨다.
5. A의 모든 이웃 노드 B에 대해 이 작업을 수행한다.
6. A의 상태를 "방문 완료"로 바꾼다. 그러면 이제 더 이상 A는 사용하지 않는다.
7. "미방문" 상태인 모든 노드들 중, 출발점으로부터의 거리가 제일 짧은 노드 하나를 골라서 그 노드를 A에 저장한다.
8. 도착 노드가 "방문 완료" 상태가 되거나, 혹은 더 이상 미방문 상태의 노드를 선택할 수 없을 때까지, 3~7의 과정을 반복한다.

3.1. 의사코드

function Dijkstra(Graph, Source):
 
    dist[source] ← 0                       // 소스와 소스 사이의 거리 초기화 --출발지와 출발지의 거리는 당연히 0--
    prev[source] ← undefined               // 출발지 이전의 최적 경로 추적은 없으므로 Undefined

    create vertex set Q                    // 노드들의 집합 Q(방문되지 않은 노드들의 집합) 생성 시작

    for each vertex v in Graph:            // Graph안에 있는 모든 노드들의 초기화
        if v ≠ source:                     // V 노드가 출발지가 아닐 경우(출발지를 제외한 모든 노드!)
            dist[v] ← INFINITY             // 소스와 V노드 사이에 알려지지 않은 거리 --얼마나 먼지 모르니까-- = 무한값 (모든 노드들을 초기화하는 값)
            prev[v] ← UNDEFINED            // V노드의  최적경로 추적 초기화
        add v to Q                         // Graph에 존재하고 방금 전 초기화된 V 노드를 Q(방문되지 않은 노드들의 집합)에 추가

//요약하자면, Graph에 존재하는 모든 노드들을 초기화한 뒤, Q에 추가함.
    
    while Q is not empty:                  // Q 집합이 공집합 아닐 경우, 루프 안으로!
        u ← vertex in Q with min dist[u]   // 첫번째 반복에서는 dist[source]=0이 선택됨. 즉, u=source에서 시작
        remove u from Q                    // U 노드를 방문한 것이므로 Q집합에서 제거
        
        for each neighbor v of u:          // U의 이웃노드들과의 거리 측정
            alt ← dist[u] + length(u, v)   // 출발지 노드 부터 계산된 U노드까지의 거리 + V에서 U의 이웃노드까지의 거리
                                           // = source to U + V to U = source to U
            if alt < dist[v]:              // 방금 V노드까지 계산한 거리(alt)가 이전에 V노드까지 계산된 거리(dist[v])보다 빠른 또는 가까운 경우
                dist[v] ← alt              // V에 기록된 소스부터 V까지의 최단거리를 방금 V노드까지 계산한 거리로 바꿈
                prev[v] ← u                // 제일 가까운 노드는 지금 방문하고 있는 노드(U)로 바꿈

    return dist[], prev[]                  // 계산된 거리값과 목적지를 리턴

3.2. 3가지 구현

• 배열 내에서 선형탐색 + 배열 내에 중복 정점 허용하지 않음
  다익스트라가 처음 고안한 알고리즘이다. [math(O(V^2+E))]의 시간복잡도를 가졌다. 음수 간선을 허용하지 않는다. 인터넷에서 설명과 구현을 쉽게 찾아볼 수 있다.
  시간복잡도에 대한 설명은 다음과 같다. 각 반복문마다 미방문 노드 중 출발점으로부터 현재까지 계산된 최단 거리를 가지는 노드를 찾는데 [math(O(V^2))]의 시간이 필요하다. 왜냐하면 언젠가 나올 모든 노드 ([math(O(V))])에 대해 원소 V개가 들어간 배열에서 선형탐색을 하며 최소값을 추출([math(O(V))])하기 때문이다. 또한 각 노드마다 이웃한 노드의 최단 거리를 갱신할 때 [math(O(E))]의 시간이 필요하다. 왜냐하면 각 노드마다 모든 이웃을 확인하는 것은 결국 모든 edge를 확인하는 것과 같고 [math(O(E))], 원소 V개가 들어간 거리 배열과 방문여부 배열(혹은 집합)을 수정([math(O(1)))])해야 하기 때문이다.

• 우선순위큐 내에서 최솟값 탐색 + 우선순위큐 내에 중복 정점 허용하지 않음
  다익스트라의 첫 고안 이후 우선순위 큐(= 힙 트리)등을 이용한 더욱 개선된 알고리즘이 나왔다. [math(O(VlogV+ElogV))]의 시간복잡도를 가졌다. 음수 간선을 허용하지 않는다. 인터넷에서 알고리즘에 대해 찾으면 나오는 대부분의 설명은 이 설명이지만, 구현은 이 구현이 아니니까 유의해야 한다.
  시간복잡도에 대한 설명은 다음과 같다. 각 반복문마다 미방문 노드 중 출발점으로부터 현재까지 계산된 최단 거리를 가지는 노드를 찾는데 [math(O(VlogV))]의 시간이 필요하다. 왜냐하면 언젠가 나올 모든 노드 ([math(O(V))])에 대해 원소 V개가 들어간 우선순위큐에서 최소값을 추출([math(O(logV))])하기 때문이다. 또한 각 노드마다 이웃한 노드의 최단 거리를 갱신할 때 [math(O(ElogV))]의 시간이 필요하다. 각 노드마다 모든 이웃을 확인하는 것은 결국 모든 edge를 확인하는 것과 같고 [math(O(E))], 원소 V개가 들어간 우선순위큐에서 change_key(새로운 비용, 비용이 바뀔 정점) 함수를 이용해 최단 거리를 갱신[math(O(logV))]해야 하기 때문이다.
  change_key 함수의 구현은 이진힙 기준으로 쉽게 할 수 있으나 문제는 비용이 바뀔 정점이 우선순위큐 내에 어디에 위치했는지 모른다는 점이다. 선형탐색을 하면 O(N)으로 도루묵이니 해시테이블/딕셔너리로 미리 구해서 O(1)로 써야하는데, decrease_key 연산을 하는 도중 관심사의 정점뿐만 아니라 그 정점과 위치가 바뀌는 정점까지도 바뀌는 위치를 전부 수정해야해서 까다롭다.

• 우선순위큐 내에서 최솟값 탐색 + 우선순위큐 내에 중복 정점 허용
  [math(O(ElogE+ElogE))]의 시간복잡도를 가졌다. 음수 간선을 허용한다. 인터넷에 찾으면 나오는 대부분의 구현은 이 구현이다.
  모든 간선이 양수일 때의 시간복잡도에 대한 설명은 다음과 같다. 이해가 편하게 삽입에 대한 설명을 먼저 하자. 각 노드마다 이웃한 노드의 최단 거리를 넣을 때 [math(O(ElogE))]의 시간이 필요하다. 왜냐하면 각 노드마다 모든 이웃을 확인하는 것은 결국 모든 edge를 확인하는 것과 같고([math(O(E))]), 그러한 모든 경우에서 최단 경로가 갱신되어 원소를 새로 넣을 경우 우선순위큐의 길이는 E가 되는데 이러한 우선순위큐에서 삽입([math(O(logE))])해야 하기 때문이다. 또한 이렇게 원소 E개인 우선순위큐 반복문 내에서 최단 거리를 가지는 노드를 찾는데 [math(O(ElogE))]의 시간이 필요하다. 왜냐하면 언젠가 나올 모든 원소([math(O(E))])에 대해 원소 E개가 들어간 우선순위큐에서 최솟값을 추출([math(O(logE))])하기 때문이다. 이렇게 추출된 값은 E개지만 (if dist[Vextracted] == dist_extracted)에 해당되는 값은 V개이기 때문에 구현2에서 말했던 '각 노드의 모든 이웃은 결국 모든 edge이다'라는 가정은 여전히 성립하고 시간복잡도에 영향은 없다. 반대로 말하자면 이러한 조건문을 걸지 않을 경우 시간복잡도가 크게 증가한다.
  음수 사이클이 없고 음수 간선이 있을 때의 시간복잡도는 [math(O(2^Vlog2^V+2^Vlog2^V))]이다 영어1, 영어2, 한국어1. 이 시간복잡도는 최악일 때의 경우이니 인위적으로 만들지 않은 그래프 혹은 음수 간선이 한두 개 있는 경우는 모든 간선이 양수일 때의 시간복잡도와 비슷하다고 봐도 좋을 것이다.
  '다익스트라 알고리즘은 그리디 알고리즘이기 때문에 A->C(비용+4) 대신 A->B(비용+3)을 선택 후 B를 방문처리하게 된다. 현재는 나쁘지만 미래에는 좋은 결과를 불러오는 A->C(비용+4)&C->B(비용-5) 경로(비용-1)를 선택하지 않게 되고 올바른 해를 도출할 수 없게 된다'라는 설명은 이 구현에서는 들어맞지 않게 된다. 중복 정점을 허용하기 때문에 그리디 알고리즘이 아니라 ( 가지치기가 빡빡한) 백트래킹으로 볼 수 있고 따라서 A->B(비용+3)부터 알고리즘을 다시 시작하게 되고 올바른 해를 도출할 수 있다.

3.3. 그림 설명

• S = 방문한 노드들의 집합
• d[N] = A → N까지 계산된 최단 거리
• Q = 방문하지 않은 노드들의 집합

• 출발지와 출발지의 거리는 확인해볼 필요도 없이 당연히 0 값을 가진다는 것을 알 수 있다. 출발지를 A로 설정했기 때문에, d[A]=0이 된다. (A노드를 아직 방문한 것은 아니다.)
• 출발지를 제외한 모든 노드들도 아직 확인되지 않았기에, d[다른 노드]=무한이 된다.
• Q는 방문하지 않은 노드들의 집합이므로, 초기화할 때는 모든 노드들의 집합이 된다.
• S는 방문한 노드가 아직 없으므로 공집합 상태이다.

• 가장 먼저, 거리가 최소인 노드(d[N]이 최소값인 노드 N)를 Q(방문하지 않은 노드의 집합)에서 제거하고, 그 노드를 S(방문한 노드의 집합 및 최소 경로)에 추가한다. 이는 즉, 노드 N을 '방문한다'는 의미가 된다.
• 이후, 방문한 노드 N과 연결된 모든 이웃 노드와의 거리를 측정하여 d[N](=출발지로부터 N까지 계산된 최소 거리값) + (N과 이웃 노드 간의 거리값) = (출발지부터 이웃 노드까지의 거리값)이 계산된다. 새로 계산된 값이 기존에 저장된 값보다 작은 경우에만 d[N]을 갱신한다.
• 예를 들어 초기화 직후의 첫 루프에서 시작 정점으로부터의 거리가 최소인 노드는 A이므로(자기 자신), 노드 A를 방문하여 Q에서 제거하고 S에 추가하게 된다. 다만, 지금은 첫 번째 루프만을 끝낸 상태이므로, 단순히 0 + (이웃 노드와 출발지 사이의 거리값) = (출발지와 이웃 노드 간의 거리값)이 각 이웃 노드까지의 거리값으로 기록된다(무한보다 작기 때문에). 따라서, d[B] = 10, d[C] = 30, d[D] =15로 값을 갱신한다.

• 이전에 설명했듯이, 방문할 노드는 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 으로 업데이트된다.[7] 여기서 d[B] 값을 더하는 이유는 출발지부터 해당 노드까지의 거리값을 재기 위해서다.

• 세 번째 루프에서 선택·방문되는 노드는 D이다. 두 번째 루프를 마친 후 Q의 원소 중에서 제일 낮은 d[N] 값을 가진 것이 D이기 때문이다. 따라서 세번째 루프를 마친 뒤인 위의 그림에서도 S에 D가 추가되어 있는 것을 볼 수 있다.
• 이제 D의 이웃 노드들(C, F)의 거리를 잰 후, d[N]값을 업데이트한다. 이 때 d[C]의 값은 A를 방문할 때 이미 계산되어 30으로 저장되해어 있었으나, D를 방문하여 C와의 거리를 확인해 보니 20으로 더 짧은 최단 경로가 발견되었다! 그러므로, d[C]의 값을 30에서 20으로 변경한다.
• d[F]의 경우에도 원래의 값이 무한이므로, 더 작은 값인 15+20=35로 변경한다.

• 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로 업데이트한다.

• 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 = ∅