다익스트라 알고리즘 정리

👩‍💻 다익스트라 알고리즘 정리 with Python

🥝 다익스트라 알고리즘 (Dijkstra Algorithm)이란? 

두 노드를 잇는 가장 짧은 경로를 찾는 문제(가중치 합이 최소가 되도록 하는 경로를 찾는 문제)에서

하나의 정점에서 다른 모든 정점 간의 각각 가장 짧은 거리를 구하는 알고리즘입니다.

 

첫 정점을 기준으로 연결되어 있는 정점들을 추가해 가며, 최단 거리를 갱신하는 기법입니다.

우선순위 큐를 활용하여 다익스트라 알고리즘을 구현해 보겠습니다.

 

1. 초기화

• 첫 정점을 기준으로 배열을 선언하여 첫 정점에서 각 정점까지의 거리를 저장합니다.
  • 초기에는 첫 정점의 거리는 0, 나머지는 무한대로 저장합니다. (inf라고 표현함)
  • 우선순위 큐에 (첫 정점, 거리 0)만 먼저 넣습니다.

 

2. 우선순위 큐에서 추출한 (A, 0) [노드, 첫 노드와의 거리]를 기반으로 인접한 노드와의 거리 계산

• 우선순위 큐에서 노드를 꺼냅니다.
  • 처음에는 첫 정점만 저장되어 있으므로, 첫 정점이 꺼내집니다.
  • 첫 정점에 인접한 노드들 각각에 대해, 첫 정점에서 각 노드로 가는 거리와 현재 배열에 저장되어 있는 첫 정점에서 각 정점까지의 거리를 비교합니다
  • 배열에 저장되어 있는 거리보다, 첫 정점에서 해당 노드로 가는 거리가 더 짧을 경우, 배열에 해당 노드의 거리를 업데이트합니다
  • 배열에 해당 노드의 거리가 업데이트된 경우, 우선순위 큐에 넣습니다.
    • 결과적으로 너비 우선 탐색 방식과 유사하게, 첫 정점에 인접한 노드들을 순차적으로 방문하게 됩니다
    • 만약 배열에 기록된 현재까지 발견된 가장 짧은 거리보다, 더 긴 거리(루트)를 가진 (노드, 거리)의 경우에는 해당 노드와 인접한 노드 간의 거리 계산을 하지 않습니다.

 

3. 우선순위 큐에서 (C, 1) [노드, 첫 노드와의 거리]를 기반으로 인접한 노드와의 거리 계산

• 우선순위 큐가 MinHeap(최소 힙) 방식이므로, 위 표에서 넣어진 (C, 1), (D, 2), (B, 8) 중 (C, 1) 이 먼저 추출됩니다.
• 위 표에서 보듯이 1단계까지의 A - B 최단 거리는 8 인 상황입니다.
  • A - C까지의 거리는 1, C에 인접한 B, D에서 C - B는 5, 즉 A - C - B는 1 + 5 = 6 이므로, A - B 최단 거리 8보다 더 작은 거리를 발견, 이를 배열에 업데이트합니다.
    • 배열에 업데이트했으므로 B, 6 (즉 A에서 B까지의 현재까지 발견한 최단 거리) 값이 우선순위 큐에 넣어집니다.
  • C - D의 거리는 2, 즉 A - C - D는 1 + 2 = 3 이므로, A - D의 현재 최단 거리인 2 보다 긴 거리, 그래서 D의 거리는 업데이트되지 않습니다.

 

4. 우선순위 큐에서 (D, 2) [노드, 첫 노드와의 거리]를 기반으로 인접한 노드와의 거리 계산

• 지금까지 접근하지 못했던 E와 F 거리가 계산됩니다.
  • A - D까지의 거리인 2에 D - E 가 3 이므로 이를 더해서 E, 5
  • A - D까지의 거리인 2에 D - F 가 5 이므로 이를 더해서 F, 7

 

5. 우선순위 큐에서 (E, 5) [노드, 첫 노드와의 거리]를 기반으로 인접한 노드와의 거리 계산

• A - E 거리가 5인 상태에서, E에 인접한 F를 가는 거리는 1, 즉 A - E - F는 5 + 1 = 6, 현재 배열에 A - F 최단거리가 7로 기록되어 있으므로, F, 6으로 업데이트합니다.
  • 우선순위 큐에 F, 6 추가

 

6. 우선순위 큐에서 (B, 6), (F, 6)를 순차적으로 추출해 각 노드 기반으로 인접한 노드와의 거리 계산

• 예제의 방향 그래프에서 B 노드는 다른 노드로 가는 루트가 없습니다.
• F 노드는 A 노드로 가는 루트가 있으나, 현재 A - A 가 0 인 반면에 A - F - A는 6 + 5 = 11, 즉 더 긴 거리이므로 업데이트되지 않습니다.

 

6. 우선순위 큐에서 (F, 7), (B, 8)를 순차적으로 추출해 각 노드 기반으로 인접한 노드와의 거리 계산

• A - F로 가는 하나의 루트의 거리가 7 인 상황이나, 배열에서 이미 A - F로 가는 현재의 최단 거리가 6인 루트의 값이 있는 상황이므로, 더 긴 거리인 F, 7 루트 기반 인접 노드까지의 거리는 계산할 필요가 없음, 그래서 계산 없이 스킵합니다.
  • 계산하더라도 A - F 거리가 6인 루트보다 무조건 더 긴 거리가 나올 수밖에 없습니다.
• B, 8 도 현재 A - B 거리가 6이므로, 인접 노드 거리 계산이 필요 없습니다.

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

mygraph = {
    'A': {'B': 8, 'C': 1, 'D': 2},
    'B': {},
    'C': {'B': 5, 'D': 2},
    'D': {'E': 3, 'F': 5},
    'E': {'F': 1},
    'F': {'A': 5}
}

import heapq


def Dijkstra(graph, start):
    distances = {node: float('inf') for node in graph}
    distances[start] = 0
    queue = []

    heapq.heappush(queue, [distances[start], start])

    while queue:
        currentDistance, currentNode = heapq.heappop(queue)

        if currentDistance > distances[currentNode]:
            continue

        for adjacent, weight in graph[currentNode].items():
            distance = currentDistance + weight

            if distance < distances[adjacent]:
                distances[adjacent] = distance
                heapq.heappush(queue, [distance, adjacent])

    return distances


print(Dijkstra(mygraph, 'A'))

 

🍉 다익스트라 알고리즘 (Dijkstra Algorithm) 시간 복잡도

• 각 정점마다 인접한 Edge들을 탐색하는 과정
  각 노드는 최대 한 번씩 방문하기 때문에 그래프의 모든 간선은 최대 한 번씩 검사합니다. 따라서 이 과정의 시간 복잡도는 O(E)입니다.
• 우선순위 큐에 [거리, 정점] 정보를 넣고 빼는 과정
  최악의 경우는 모든 간선을 검사할 때마다 거리 값 리스트가 갱신되고, 우선순위 큐에 정보가 저장되는 경우입니다. E개의 Edge를 검사할 때마다 우선순위 큐를 유지해야 하므로 이 과정의 시간 복잡도는 O(ElogE)입니다.

위 두 과정을 거칠 경우 다익스트라 알고리즘의 총 시간 복잡도는 O(E)+O(ElogE)=O(ElogE)가 됩니다.