🛣️ 다익스트라(Dijkstra) 알고리즘: 내비게이션은 어떻게 최단 경로를 찾을까?

오늘은 그래프에서 최단 경로를 찾는 대표적인 알고리즘, 다익스트라(Dijkstra)에 대해 정리해보려고 한다.

우리가 맨날 쓰는 네이버맵이나 카카오맵이 어떻게 그 복잡한 길들 중에서 제일 빠른 길을 뿅! 하고 찾아주는지 궁금했다면, 그 비밀의 열쇠가 바로 여기에 있다.

저번에 그래프 기본기를 다졌으니, 이번엔 그걸 제대로 활용하는 방법을 파헤쳐 보자! 🚀

🤔 다익스트라 알고리즘, 그래서 뭔데?

아주 간단하게 말하면, 다익스트라는 **"한 지점에서 출발해서 다른 모든 지점까지 가는 가장 빠른 길"**을 찾는 알고리즘이다.

여기서 딱 두 가지만 기억하면 된다.

1. 출발지는 딱 한 곳!

   "서울역에서 출발!" 이라고 딱 정하면, 거기서부터 부산, 광주, 강릉까지 가는 각각의 최단 루트를 다 찾아주는 거다.

2. '최단'의 의미

   그냥 몇 정거장 안 거치는 게 아니라, 각 길마다 있는 '비용'이나 '시간' 같은 가중치(Weight)의 합이 제일 작은 길을 뜻한다.

‼️ 여기서 엄청 중요한 규칙이 하나 있다.

다익스트라는 마이너스(-) 비용은 계산하지 못한다!

모든 길의 비용은 0이거나 플러스(+)여야만 한다.

왜 그런지는 이따가 살펴보자. 😉

💡 핵심 아이디어: 일단 제일 가까운 데부터!

다익스트라의 핵심 전략은 진짜 간단하다. 딱 이 한 문장으로 요약된다.

"일단 지금 갈 수 있는 길 중에서 제일 가까운 데부터 가보자!"

이걸 좀 있어 보이게 '그리디(Greedy) 알고리즘'이라고 부른다. 그냥 매 순간마다 제일 좋아 보이는 걸 고르는 거다. 그렇게 계속 가다 보면 결국 최종 목적지까지 제일 빠른 길을 찾게 되는 원리다.

그럼 어떻게 돌아가는지 흐름을 한번 훑어보자.

1. 일단 표를 하나 만든다.

   출발점에서 각 지점까지 얼마나 걸리는지 적을 distance 표를 만든다. 처음엔 출발점은 0, 나머지는 아예 갈 수 없으니까 **무한대(∞)**라고 적어둔다.

2. 이제 출발!

   • 아직 안 가본 곳들 중에서, distance 표에 적힌 거리가 제일 짧은 곳을 하나 골라서 간다.

   • 거기 도착하면, 그곳을 거쳐서 갈 수 있는 옆 동네들을 살펴본다. "어? 이 길로 가니까 더 빠르네?" 싶으면 distance 표에 적힌 값을 더 짧은 걸로 업데이트해주는 거다!

3. 무한 반복!

   모든 지점을 다 방문할 때까지 2번 과정을 계속 돌리면 끝! 그럼 distance 표에는 출발점에서 모든 곳까지 가는 최단 시간이 딱! 적히게 된다.

👣 예제로 따라가며 완전 정복하기

백문이 불여일견. 간단한 그래프 예제로 알고리즘의 각 단계를 차근차근 따라가 보자.

A에서 출발해서 다른 모든 노드까지의 최단 거리를 구해보는 거다.

# 예제에 사용할 그래프와 변수들
graph = {
    'A': {'B': 2, 'C': 5},
    'B': {'C': 6, 'D': 1},
    'C': {},
    'D': {'F': 8},
    'E': {},
    'F': {}
}
nodes = graph.keys()
INF = float('inf')

[시작 전 세팅]

# 코드 초기 상태
distance = {node: INF for node in nodes}
distance['A'] = 0
visited = []

# 초기 distance: {'A': 0, 'B': inf, 'C': inf, 'D': inf, 'E': inf, 'F': inf}
# 초기 visited: []

[첫 번째 스텝] A에서 출발!

# **첫 번째 스텝**: A 방문 후
distance['B'] = 2
distance['C'] = 5
visited.append('A')

# **첫 번째 스텝** distance: {'A': 0, 'B': 2, 'C': 5, 'D': inf, 'E': inf, 'F': inf}
# **첫 번째 스텝** visited: ['A']

• A에서 바로 갈 수 있는 B랑 C를 distance 표에 업데이트한다.

  • A → B는 비용 2이므로, distance[B]를 2로 바꾼다!

  • A → C는 비용 5이므로, distance[C]를 5로 바꾼다!

• A는 이제 볼일 끝! visited에 추가!

[두 번째 스텝] 제일 가까운 데가 어디지?

# 두 **번째 스텝**: B 방문 후
distance['D'] = 3
visited.append('B')

# 두 **번째 스텝** distance: {'A': 0, 'B': 2, 'C': 5, 'D': 3, 'E': inf, 'F': inf}
# 두 **번째 스텝** visited: ['A', 'B']

• 아직 안 가본 곳 중에 distance 값이 제일 작은 곳은? 바로 B (거리 2) 다. B로 가보자!

• B에 도착! B를 거쳐서 갈 수 있는 C랑 D를 한번 보자.

  • B에서 C로 가려면? A에서 B까지 온 비용(2) + B에서 C까지 비용(6) = 총 8.

    엥? 근데 아까 A에서 바로 C로 가는 길은 5였다. 더 비싸니까 업데이트 안 한다!

  • B에서 D로 가려면? A에서 B까지 온 비용(2) + B에서 D까지 비용(1) = 총 3. distance[D]는 원래 ∞였는데 3으로 업데이트!

• B도 볼일 끝! visited에 추가!

[세 번째 스텝] 다음 타자는?

• 안 가본 곳 중에 제일 가까운 곳은 D (거리 3)! D로 가보자!

• D에서는 F로 갈 수 있다.

  • D에서 F로 가려면? A→B→D까지 온 비용(3) + D에서 F까지 비용(8) = 총 11.

  • distance[F]를 11로 업데이트!

• D도 방문 완료!

...어떤가? 이런 식으로 쭉~ 반복하면 되는 거다.

💻 파이썬으로 구현하기: 우선순위 큐(Heapq)

근데 잠깐만… '제일 가까운 곳' 찾으려고 매번 표를 다 뒤져봐야 해? 노드가 엄청 많으면 시간 다 가겠는데?

이 문제를 해결해 주는 치트키가 있다.

바로 앞서 배운 적 있는 **우선순위 큐(Priority Queue)**다.(파이썬에서는 heapq로 이용 가능한!)

알다시피 우선순위 큐는 그냥 데이터를 막 집어넣어도, 우리가 정한 기준(여기서는 '가장 짧은 거리')에 맞는 걸 1등으로 뽑아준다.

여기에 (거리, 노드) 쌍을 넣어주면, 알아서 거리가 제일 짧은 놈을 빛의 속도로 찾아준다!

이제 heapq를 사용한 최종 버전의 파이썬 코드를 만나보자.

import heapq # 우선순위 큐 구현을 위함

def dijkstra(graph, start):
    # 1. 출발점에서 각 노드까지의 거리를 저장할 딕셔너리 (초기값: 무한대)
    distances = {node: float('inf') for node in graph}
    # 2. 출발 노드의 거리는 0으로 설정
    distances[start] = 0

    # 3. 우선순위 큐 생성. (거리, 노드) 형태로 튜플을 저장
    #    거리가 짧은 노드부터 먼저 나와야 하므로 거리를 튜플의 첫 번째 원소로 둔다.
    priority_queue = [(0, start)]

    while priority_queue:
        # 4. 큐에서 거리가 가장 짧은 노드 정보를 꺼냄
        current_distance, current_node = heapq.heappop(priority_queue)

        # 5. 이미 처리된 노드라면 무시 (더 짧은 경로를 이미 발견한 경우)
        #    (예: A->C (5) 보다 A->B->D->C (4)가 나중에 발견될 수 있음)
        if current_distance > distances[current_node]:
            continue

        # 6. 현재 노드와 인접한 노드들을 확인하며 거리 갱신
        for neighbor, weight in graph[current_node].items():
            distance = current_distance + weight

            # 7. 새로운 경로가 기존 경로보다 더 짧으면 갱신
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                # 8. 갱신된 정보를 우선순위 큐에 추가
                heapq.heappush(priority_queue, (distance, neighbor))

    return distances

# 그래프 예시 (인접 리스트 방식)
# 'A': {'B': 8, 'C': 1} -> A에서 B까지 8, C까지 1
my_graph = {
    'A': {'B': 8, 'C': 1, 'D': 2},
    'B': {},
    'C': {'B': 5, 'D': 2},
    'D': {'E': 3, 'F': 5},
    'E': {'F': 1},
    'F': {'A': 5}
}

# 다익스트라 알고리즘 실행
shortest_paths = dijkstra(my_graph, 'A')
print(shortest_paths)
# 출력 결과: {'A': 0, 'B': 6, 'C': 1, 'D': 2, 'E': 5, 'F': 6}

⚠️ 다익스트라가 못하는 것: 음수 가중치

근데 왜 마이너스(-) 비용은 안된다고 했을까?

다익스트라는 좀 순진한 친구라서, "한 번 정한 최단 거리는 절대 변하지 않아!"라고 굳게 믿어버린다.

예를 들어, A→B로 가는 길이 5가 제일 빠르다고 도장을 꽝! 찍었는데, 나중에 저쪽에서 C→D로 가는 -3짜리 지름길이 발견돼서 그걸 거쳐오니 A→B가 4가 될 수도 있지 않나? 그럼 다익스트라는 "으앙! 이미 정했는데 어떡해!" 하면서 멘붕에 빠지는 거다. 😭 이미 지나온 길은 다시 돌아보지 않기 때문이다.

(참고로 이런 마이너스 길까지 계산해 주는 건 벨만-포드라는 다른 알고리즘이 처리한다!)

✨ 정리하며

구분	다익스트라 (Dijkstra)
목적	하나의 출발지에서 다른 모든 노드까지의 최단 경로 탐색
핵심 원리	탐욕법(Greedy) + 동적 계획법(DP)
핵심 자료구조	우선순위 큐 (Heapq)
시간 복잡도	O(ElogV) (E: 간선 수, V: 노드 수)
장점	BFS/DFS보다 훨씬 복잡한 가중치 그래프에서 최적의 해를 찾을 수 있음
치명적 단점	음수 가중치(음수 간선)가 있는 그래프에서는 사용 불가 ❌