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

최단 경로 알고리즘이란?

최단 경로 알고리즘은 그래프 상에서 특정 정점에서 다른 정점까지 가장 적은 비용(거리, 시간 등)으로 도달할 수 있는 경로를 찾는 알고리즘을 말한다. 일반적으로 네비게이션과 같은 길찾기에 적용된다.

다익스트라 알고리즘의 동작 원리

다익스트라 알고리즘은 "하나의 시작점에서 다른 모든 정점으로 가는 최단 경로"를 구하는 알고리즘이다. 음수의 가중치가 없을 때만 사용할 수 있으며, 기본적으로 그리디 알고리즘과 다이나믹 프로그래밍의 원리가 섞여있다.

• 초기화 : 출발 정점의 거리는 0, 나머지 모든 정점의 거리는 무한대로 설정한다.
• 정점 선택 : 아직 방문하지 않은 정점 중 최단 거리가 가장 짧은 정점을 선택한다.
• 거리 갱신 : 선택한 정점을 거쳐서 인접한 다른 정점으로 이동하는 거리가, 기존에 기록된 거리보다 짧다면 그 값을 갱신한다.
• 반복 : 모든 정점을 방문할 때까지 2~3번의 과정을 반복한다.

우선 노드 간의 거리는 무한대의 값으로 초기화하고 출발 노드는 1번 노드에서 시작한다. 1번 노드는 본인과의 거리가 0이기 때문에 거리를 0으로 채워놓는다.

1번 노드와 직접 연결된 노드는 2,3,4번 노드이고, 1번 노드에서 각각의 노드까지 걸리는 거리를 갱신해준다. 그 후 최단 거리인 3번 노드로 이동해서 다음 단계를 진행한다.

3번 노드와 직접 연결된 노드는 4번 노드와 6번 노드이다. 또 각각의 노드까지의 거리를 최단거리로 갱신해주고, 거리 테이블 상의 다음 작은 값을 가진 2번 노드를 방문한다.

 

같은 방법으로 2번 노드와 연결되어있는 4번과 6번 노드의 거리를 최단거리로 갱신해주고, 거리 테이블 상의 다음 작은 값인 4번 노드를 방문한다.

위와 같은 방법으로 노드를 이동해가면서 최단거리를 갱신해주고, 모든 노드를 방문할 때 까지 반복한다.

가중치(Graph Weight)란 무엇인가?

가중치는 그래프의 정점과 정점을 연결하는 간선에 부여된 고유한 값을 의미한다.

BFS와 다익스트라 알고리즘의 차이점

구분	BFS (너비 우선 탐색)	다익스트라 (Dijkstra)
가중치 조건	가중치가 없거나 모두 동일할 때 (1로 동일)	가중치가 양수일 때 (제각각 다름)
탐색 기준	시작점으로부터의 간선개수가 적은 순	시작점으로부터의 누적 가중치 합이 작은 순
자료구조	일반적인 큐 (Queue)	우선순위 큐(Priority Queue)

우선순위 큐(Priority Queue)와 힙(Heap)이 왜 사용되는가?

다익스트라 알고리즘의 핵심은 "아직 방문하지 않은 노드들 중 출발지로부터의 거리가 가장 짧은 노드를 선택하는 것"이다. 이 작업을 효율적으로 처리하기 위해 두 자료구조가 사용된다.

우선순위 큐(Prioirty Queue)

• 데이터를 입력한 순서와 상관없이, 정해진 우선순위(다익스트라에서는 '최단 거리')가 가장 높은 데이터가 먼저 나오는 큐이다.
• 추상적인 개념(인터페이스)이며, 이를 실제로 컴퓨터 메모리 상에서 가장 빠르게 구현한 물리적 자료구조가 힙(Heap)이다.

힙(Heap)을 사용하는 이유

• 일반 배열을 사용할 때: 노드가 V개 있을 때 최솟값을 찾으려면 배열을 처음부터 끝까지 다 뒤져야 하므로 O(V)의 시간이 걸린다. 이를 모든 노드마다 반복하게되면 비효율적이다.
• 최소 힙(Min-Heap)을 사용할 때 : 부모 노드가 항상 자식 노드보다 작은 완전 이진 트리 구조를 유지한다. 덕분에 최솟값을 찾는 연산은 항상 루트 노드만 보면 되므로 O(1)이며, 데이터를 삽입하고 최솟값을 삭제하며 트리를 재정렬하는 데 O(logV)밖에 걸리지 않는다
• 결론적으로 탐색 속도를 크게 끌어올려 전체 알고리즘의 병목 현상을 해결해준다.

다익스트라 알고리즘의 시간복잡도

다익스트라 알고리즘의 시간복잡도는 그래프의 정점(Vertex) 개수 V와 간선(Edge) 개수 E,그리고 어떤 자료구조를 쓰느냐에 따라 결정된다.

순차 탐색(배열) 방식을 사용할 때 : O(V^2)

• 방문하지 않은 노드 중 최단 거리 노드를 찾기 위해 V번 돌며 배열을 탐색한다 → O(V)
• 이 작업을 모든 노드(V개)에 대해 수행하므로 기본적인 노드 탐색에만 O(V^2)이 걸린다.
• 간선을 확인하는 연산은 총 O(E)이므로 전체 복잡도는 O(V^2+E)가 되며, 대게 V^2이 더 크므로 O(V^2)이 된다.

우선순위 큐(힙) 방식을 사용할 때 : O(ElogV)

• 기존의 O(V) 걸리던 최단 노드 탐색이 힙 때문에 O(logV)로 줄어든다.
• 그래프의 모든 간선(E개)을 검사하면서, 더 짧은 경로를 발견할 때마다 힙에 거리 정보를 추가하거나 갱신하는 연산이 일어난다.
• 힙에 최대 E번 데이터가 들어갔다 나올 수 있으므로, 힙 연산 성능인 logV와 결합하여 최종 시간 복잡도는 O(ElogV)가 된다. 정점 대비 간선이 아주 빽빽한 완전 그래프가 아니라면 대부분 O(ElogV)가 O(V^2)보다 훨씬 빠르다.

코드 구현

heapq를 사용하지 않은 다익스트라 구현 (미구현)

# 무한대를 의미하는 값 설정
INF = int(1e9)

# 동일한 그래프 데이터 정의
graph = {
    1: [(2, 4), (3, 2)],
    2: [(3, 3), (4, 2), (5, 3)],
    3: [(2, 1), (4, 4), (5, 5)],
    4: [(5, 1)],
    5: []
}

def dijkstra_no_heap(start, n):
    # 최단 거리 테이블 초기화
    distance = [INF] * (n + 1)
    distance[start] = 0
    
    # 각 노드의 방문 여부를 체크할 배열 생성
    visited = [False] * (n + 1)
    
    # 경로 추적을 위한 직전 노드 기록 배열
    parent = [None] * (n + 1)
    
    # 핵심 변경 포인트: 방문하지 않은 노드 중 최단 거리 노드를 '수동'으로 찾는 함수
    def get_smallest_node():
        min_value = INF
        index = 0  # 가장 최단 거리가 짧은 노드의 번호
        for i in range(1, n + 1):
            if distance[i] < min_value and not visited[i]:
                min_value = distance[i]
                index = i
        return index

    # 노드의 개수만큼 반복
    for _ in range(n):
        # 현재 가장 거리가 짧은 노드를 선형 탐색으로 찾아옴 -> O(V) 발생
        now = get_smallest_node()
        if now == 0: # 더 이상 갈 수 있는 노드가 없다면 종료
            break
            
        visited[now] = True # 방문 처리
        
        # 현재 노드와 연결된 다른 노드 확인
        for next_node, weight in graph.get(now, []):
            cost = distance[now] + weight
            if cost < distance[next_node]:
                distance[next_node] = cost
                parent[next_node] = now # 경로 기록

    return distance, parent

# 경로 역추적 함수
def find_actual_path(parent, target):
    path = []
    current = target
    while current is not None:
        path.append(current)
        current = parent[current]
    return path[::-1]

# 실행 및 결과 출력
start_node = 1
num_of_nodes = 5
distances, parent_records = dijkstra_no_heap(start_node, num_of_nodes)

print(f"=== [heapq 미사용] 최단 거리 및 실제 이동 경로 ===")
for i in range(1, num_of_nodes + 1):
    if distances[i] == INF:
        print(f"정점 {i}: 도달 불가능")
    else:
        path = find_actual_path(parent_records, i)
        print(f"정점 {i} | 최단 거리: {distances[i]:<2} | 실제 경로: {' -> '.join(map(str, path))}")

결괏값

=== [heapq 미사용] 최단 거리 및 실제 이동 경로 ===
정점 1 | 최단 거리: 0  | 실제 경로: 1
정점 2 | 최단 거리: 3  | 실제 경로: 1 -> 3 -> 2
정점 3 | 최단 거리: 2  | 실제 경로: 1 -> 3
정점 4 | 최단 거리: 5  | 실제 경로: 1 -> 3 -> 2 -> 4
정점 5 | 최단 거리: 6  | 실제 경로: 1 -> 3 -> 2 -> 5

heapq를 사용한 다익스트라 구현 (미구현)

import heapq

# 무한대를 의미하는 값으로 10억 설정
INF = int(1e9)

# 그래프 데이터 정의 (인접 리스트 방식)
graph = {
    1: [(2, 4), (3, 2)],
    2: [(3, 3), (4, 2), (5, 3)],
    3: [(2, 1), (4, 4), (5, 5)],
    4: [(5, 1)],
    5: []
}

def dijkstra_heap(start, n):
    # 최단 거리 테이블을 모두 무한대로 초기화
    distance = [INF] * (n + 1)
    distance[start] = 0
    
    # 실제 경로 추적을 위한 직전 노드 기록 배열 (None으로 초기화)
    parent = [None] * (n + 1)
    
    # heapq를 위한 우선순위 큐 생성 및 시작 노드 삽입 (거리, 노드)
    queue = []
    heapq.heappush(queue, (0, start))
    
    while queue:
        # 가장 최단 거리가 짧은 노드 정보 꺼내기
        dist, now = heapq.heappop(queue)
        
        # 현재 꺼낸 거리가 이미 최단 거리로 처리된 적이 있다면 패스
        if distance[now] < dist:
            continue
            
        # 현재 노드와 연결된 다른 인접 노드들을 확인
        for next_node, weight in graph.get(now, []):
            cost = dist + weight
            # 더 짧은 경로를 발견한 경우
            if cost < distance[next_node]:
                distance[next_node] = cost
                parent[next_node] = now  # 어떤 노드(now)를 거쳐왔는지 기록
                heapq.heappush(queue, (cost, next_node))
                
    return distance, parent

# parent 배열을 바탕으로 시작점부터 목적지까지 역추적하여 경로를 만드는 함수
def find_actual_path(parent, target):
    path = []
    current = target
    while current is not None:
        path.append(current)
        current = parent[current]
    return path[::-1]  # 역순으로 모인 경로를 올바른 순서로 뒤집음

# --- 실행 및 결과 출력 ---
start_node = 1
num_of_nodes = 5
distances, parent_records = dijkstra_heap(start_node, num_of_nodes)

# 결과 출력
print(f"=== 시작 정점 {start_node}번 기준 최단 거리 및 실제 이동 경로 ===")
for i in range(1, num_of_nodes + 1):
    if distances[i] == INF:
        print(f"정점 {i}: 도달할 수 없는 노드입니다.")
    else:
        path = find_actual_path(parent_records, i)
        path_str = " -> ".join(map(str, path))
        print(f"정점 {i} | 최단 거리: {distances[i]:<2} | 실제 경로: {path_str}")

결괏값

=== 시작 정점 1번 기준 최단 거리 및 실제 이동 경로 ===
정점 1 | 최단 거리: 0  | 실제 경로: 1
정점 2 | 최단 거리: 3  | 실제 경로: 1 -> 3 -> 2
정점 3 | 최단 거리: 2  | 실제 경로: 1 -> 3
정점 4 | 최단 거리: 5  | 실제 경로: 1 -> 3 -> 2 -> 4
정점 5 | 최단 거리: 6  | 실제 경로: 1 -> 3 -> 2 -> 5

heapq를 사용하지 않은 방식과 성능 비교 (미구현)

import heapq
import random
import time
import sys

# 파이썬의 기본 재귀 제한 및 출력 제한 해제 (대규모 데이터 처리용)
sys.setrecursionlimit(10**6)
INF = int(1e9)

# ==========================================
# 1. 무작위 그래프 생성 함수
# ==========================================
def generate_random_graph(num_nodes, num_edges):
    """
    num_nodes: 정점 개수
    num_edges: 간선 개수
    """
    graph = {i: [] for i in range(1, num_nodes + 1)}
    
    # 중복 간선을 방지하면서 랜덤하게 간선 생성
    edge_set = set()
    while len(edge_set) < num_edges:
        u = random.randint(1, num_nodes)
        v = random.randint(1, num_nodes)
        if u != v and (u, v) not in edge_set:
            weight = random.randint(1, 10) # 가중치는 1~10 사이 랜덤
            graph[u].append((v, weight))
            edge_set.add((u, v))
            
    return graph

# ==========================================
# 2. Heapq를 사용한 다익스트라 (O(E log V))
# ==========================================
def dijkstra_with_heap(graph, start, n):
    distance = [INF] * (n + 1)
    distance[start] = 0
    queue = []
    heapq.heappush(queue, (0, start))
    
    while queue:
        dist, now = heapq.heappop(queue)
        if distance[now] < dist:
            continue
        for next_node, weight in graph.get(now, []):
            cost = dist + weight
            if cost < distance[next_node]:
                distance[next_node] = cost
                heapq.heappush(queue, (cost, next_node))
    return distance

# ==========================================
# 3. Heapq를 사용하지 않은 다익스트라 (O(V^2))
# ==========================================
def dijkstra_no_heap(graph, start, n):
    distance = [INF] * (n + 1)
    distance[start] = 0
    visited = [False] * (n + 1)
    
    def get_smallest_node():
        min_value = INF
        index = 0
        for i in range(1, n + 1):
            if distance[i] < min_value and not visited[i]:
                min_value = distance[i]
                index = i
        return index

    for _ in range(n):
        now = get_smallest_node()
        if now == 0:
            break
        visited[now] = True
        for next_node, weight in graph.get(now, []):
            cost = distance[now] + weight
            if cost < distance[next_node]:
                distance[next_node] = cost
    return distance

# ==========================================
# 4. 100개, 3000개, 50000개 실험 진행
# ==========================================
# 실험 케이스: (정점 수, 간선 수)
test_cases = [
    (100, 400),       # 1) 정점 100개, 간선 400개
    (3000, 12000),    # 2) 정점 3000개, 간선 12000개
    (50000, 200000)    # 3) 정점 50000개, 간선 200000개
]

for V, E in test_cases:
    print(f"\n==========================================")
    print(f" 실험 케이스: 정점(V) {V}개 / 간선(E) {E}개")
    print(f"==========================================")
    
    # 그래프 데이터 생성
    graph = generate_random_graph(V, E)
    start_node = 1
    
    # ----------------------------------------
    # [A] Heapq 사용 방식 측정
    # ----------------------------------------
    start_time = time.time()
    res_heap = dijkstra_with_heap(graph, start_node, V)
    heap_time = time.time() - start_time
    print(f"▶ heapq 사용 알고리즘 소요 시간  : {heap_time:.5f}초")
    
    # ----------------------------------------
    # [B] Heapq 미사용 방식 측정
    # ----------------------------------------        
    start_time = time.time()
    res_no_heap = dijkstra_no_heap(graph, start_node, V)
    no_heap_time = time.time() - start_time
    print(f"▶ heapq 미사용 알고리즘 소요 시간: {no_heap_time:.5f}초")
    
    # 두 알고리즘의 결과가 완전히 일치하는지 검증
    if res_heap == res_no_heap:
        print(" 결과 검증: 두 방식의 최단 거리 결과가 완벽히 일치합니다.")
    else:
        print(" 결과 검증: 오류 발생 (결과가 다릅니다.)")

결괏값

==========================================
 실험 케이스: 정점(V) 100개 / 간선(E) 400개
==========================================
▶ heapq 사용 알고리즘 소요 시간  : 0.00000초
▶ heapq 미사용 알고리즘 소요 시간: 0.00000초
 결과 검증: 두 방식의 최단 거리 결과가 완벽히 일치합니다.

==========================================
 실험 케이스: 정점(V) 3000개 / 간선(E) 12000개
==========================================
▶ heapq 사용 알고리즘 소요 시간  : 0.00399초
▶ heapq 미사용 알고리즘 소요 시간: 0.24955초
 결과 검증: 두 방식의 최단 거리 결과가 완벽히 일치합니다.

==========================================
 실험 케이스: 정점(V) 50000개 / 간선(E) 200000개
==========================================
▶ heapq 사용 알고리즘 소요 시간  : 0.10066초
▶ heapq 미사용 알고리즘 소요 시간: 69.22850초
 결과 검증: 두 방식의 최단 거리 결과가 완벽히 일치합니다.