[100일의 IT 초보 탈출] #54 다익스트라 알고리즘 _ 가장 빠른 길을 찾는 네비게이션의 뇌

오늘은 무엇을 배우게 될까요?

 

그래프는 정점(노드)과 간선(연결선)으로 구성된 구조였고,

우리는 이 구조 안에서 BFS나 DFS를 통해 탐색하는 방법을 배웠습니다.

 

그런데 만약 “가장 빠른 길”이나 “가장 비용이 적은 경로”를 찾고 싶다면 어떨까요?

이때 사용하는 알고리즘이 바로 다익스트라 알고리즘(Dijkstra’s Algorithm)입니다.

 

오늘은 이 알고리즘이 어떤 원리로 최단 경로를 구하는지,

직접 구현하는 방법과 함께 배워봅니다.

 

---

 

다익스트라 알고리즘이란?

 

다익스트라 알고리즘은

가중치가 있는 그래프에서 최단 경로를 찾는 알고리즘입니다.

시작 노드에서 다른 모든 노드까지의 최소 비용 경로를 계산합니다.

 

→ 실생활에선 네비게이션, 통신망 최적화, 게임 AI 등에서 사용됩니다.

 

---

 

 

전제 조건

 

• 모든 간선의 가중치가 0보다 크거나 같아야 함
• 간선에 음의 가중치가 있으면 사용 불가! (→ 벨만-포드 알고리즘 필요)

 

---

 

 

작동 원리 요약

 

1. 시작 노드를 기준으로 거리 테이블(비용)을 초기화
2. 가장 거리가 짧은 노드를 선택
3. 그 노드를 통해 인접 노드까지의 비용을 최신화
4. 모든 노드를 방문할 때까지 위 과정 반복

 

→ 핵심은: 현재까지 가장 짧은 경로를 기준으로 확장해나간다

 

---

시각적 흐름 예시

A ---5---> B ---2---> C
|                        |
7                        1
|                        |
V                        V
D <-------4-------<---- E

 

• A에서 시작하면 A→B→C→E→D 순으로 최단 경로 확정됨

 

---

 

 

구현: 우선순위 큐(Priority Queue) 사용

 

Python에서는 heapq를 사용하면 됩니다.

import heapq

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

    while queue:
        curr_dist, curr_node = heapq.heappop(queue)

        if curr_dist > distances[curr_node]:
            continue

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

    return distances

graph = {
    'A': [('B', 5), ('D', 7)],
    'B': [('C', 2)],
    'C': [('E', 1)],
    'D': [],
    'E': [('D', 4)]
}

result = dijkstra(graph, 'A')
print(result)

출력 예시:

{'A': 0, 'B': 5, 'C': 7, 'D': 9, 'E': 8}

 

---

시간 복잡도

 

• 우선순위 큐 사용 시: O(E log V)
• (E: 간선 수, V: 노드 수)

 

---

 

 

다익스트라 알고리즘을 사용하는 곳

분야예시

내비게이션	가장 빠른 길 찾기
네트워크	패킷 전달 최적 경로
게임	캐릭터의 이동 최단 거리 계산
로봇공학	장애물을 피해 목적지까지 이동
SNS	가장 가까운 친구 경로 계산

 

---

 

 

한 줄 요약

 

👉 다익스트라 알고리즘은 가중치 있는 그래프에서 최단 경로를 구하는 최적의 도구로,

우선순위 큐를 이용해 효율적으로 동작합니다.