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

개요

다익스트라(Dijkstra) 알고리즘은 그래프 상에서 하나의 시작 정점으로부터 다른 모든 정점까지의 최단 경로를 계산하는 알고리즘이다. 가중치가 있는 그래프에서 각 정점까지의 최소 비용을 계산하며, 우선순위 큐를 사용해 탐색 효율을 극대화한다. GPS 내비게이션, 네트워크 라우팅, 교통망 분석 등 다양한 실무 분야에서 핵심적으로 사용된다. 본 글에서는 다익스트라 알고리즘의 개념, 동작 원리, 구현 방식, 시간 복잡도, 활용 사례를 체계적으로 정리한다.

---

1. 개념 및 정의

다익스트라 알고리즘은 음수 간선이 없는 가중치 그래프에서 시작 노드로부터 모든 노드까지의 최단 경로를 구하는 탐색 알고리즘이다. 각 정점까지의 거리를 지속적으로 업데이트하며, 우선순위 큐(Priority Queue)를 사용해 가장 짧은 거리의 정점을 먼저 선택한다.

---

2. 알고리즘 동작 과정

단계	설명
1	시작 노드의 거리를 0으로 초기화, 나머지는 무한대(∞)로 설정
2	방문하지 않은 노드 중 현재 거리값이 가장 짧은 노드를 선택
3	해당 노드를 기준으로 인접한 노드들의 거리 값을 업데이트
4	모든 노드를 방문할 때까지 반복

우선순위 큐(힙)를 사용하면 성능을 크게 향상시킬 수 있다.

---

3. 파이썬 구현 예시 (heapq 활용)

import heapq

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

    while queue:
        current_dist, current_node = heapq.heappop(queue)

        if current_dist > distances[current_node]:
            continue

        for neighbor, weight in graph[current_node]:
            distance = current_dist + weight
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                heapq.heappush(queue, (distance, neighbor))

    return distances

이 구현은 우선순위 큐를 활용해 시간 복잡도를 O((V+E) log V) 수준으로 줄인다.

---

4. 시간 및 공간 복잡도

조건	복잡도
인접 리스트 + 우선순위 큐	O((V + E) log V)
인접 행렬 사용 시	O(V²)

우선순위 큐(힙 자료구조)를 사용하는 방식이 실무에서 가장 많이 사용된다.

---

5. 다익스트라 vs 벨만-포드 vs A*

항목	다익스트라	벨만-포드	A* 알고리즘
음수 가중치 허용	X	O	X
최단 경로 보장	O	O	O (휴리스틱 정확 시)
우선순위 큐 사용	O	X	O
사용 목적	일반 최단 경로	음수 간선 포함 문제	빠른 추정 경로 탐색

다익스트라는 가장 안정적이고 정확한 최단 경로 알고리즘 중 하나다.

---

6. 활용 사례

분야	적용 예시
내비게이션	실시간 거리 기반 경로 계산
네트워크 라우팅	최적 패킷 전달 경로 탐색 (ex. OSPF)
교통 시뮬레이션	출퇴근 시간 최단 이동 경로 분석
로봇 경로 탐색	장애물 회피 기반 가중치 경로 탐색
알고리즘 문제풀이	그래프 기반 최소 비용 계산 문제

실제 시스템에서는 A*와 결합하여 성능을 높이기도 한다.

---

7. 결론

다익스트라 알고리즘은 음수가 없는 가중치 그래프에서 최단 경로를 구하는 데 있어 가장 대표적이고 안정적인 알고리즘이다. 효율적인 탐색을 위해 우선순위 큐를 사용하며, 다양한 응용 분야에서 실제 성능을 입증해왔다. 문제의 조건(가중치, 방향성, 음수 간선 유무 등)에 맞춰 적절한 알고리즘 선택이 중요하며, 다익스트라는 그 중심축에 있다.