anonymous.rs

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

11 min read

다익스트라 알고리즘 (Dijkstra’s Algorithm) 완벽 가이드

그래프 탐색에서 **최단 경로(Shortest Path)**를 찾는 문제는 코딩 테스트와 실무(네비게이션, 네트워크 라우팅 등)에서 매우 중요합니다. 방문할 수 있는 노드 중에 가장 비용이 작은 곳을 먼저 방문하는(우선순위가 높은 곳을 방문) 방식을 사용합니다.

가중치가 없는 그래프라면 단순히 너비 우선 탐색(BFS)을 사용하면 되지만, 간선마다 비용(가중치)이 다른 경우에는 어떻게 해야 할까요?

이때 등장하는 해결사가 바로 **다익스트라 알고리즘(Dijkstra’s Algorithm)**입니다.

1. 가중치 그래프와 BFS의 한계

만약 A에서 F로 이동하려고 합니다. 간선에 적힌 숫자가 이동하는 데 드는 비용(시간, 거리 등)이라고 가정해 봅시다.

  • A B (비용: 10)
  • A C (비용: 2)
  • C B (비용: 3)

A에서 B로 가는 경로를 찾을 때, 일반적인 BFS는 거치는 간선의 수가 가장 적은 A -> B 경로를 최단 경로로 선택합니다. 하지만 실제 비용은 10입니다. 반면 A -> C -> B로 가면 간선은 두 개를 거치지만 총비용은 2 + 3 = 5가 되어 훨씬 효율적입니다.

이처럼 **간선에 가중치가 있는 그래프(Weighted Graph)**에서는 최단 경로를 구하기 위해 BFS 대신 다익스트라 알고리즘을 사용해야 합니다.

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

다익스트라 알고리즘은 특정 하나의 시작 정점에서 다른 모든 정점까지의 최단 경로를 구하는 알고리즘입니다. (One-to-All Shortest Path)

핵심 전제 조건

  • 간선의 가중치가 음수(-)가 아니어야 합니다. (현실 세계의 거리나 시간은 음수가 될 수 없으므로 대부분의 상황에 부합합니다. 음수 가중치가 있다면 벨만-포드 알고리즘을 사용해야 합니다.)

동작 원리 (그리디 + 우선순위 큐)

다익스트라 알고리즘은 **“매 순간, 아직 방문하지 않은 정점 중 가장 비용이 적게 드는 정점을 선택한다”**는 그리디(Greedy) 방식을 기반으로 합니다. 이 ‘가장 비용이 적은 정점’을 빠르게 찾기 위해 주로 **최소 힙(Min Heap) 기반의 우선순위 큐(Priority Queue)**를 사용합니다.

3. 다익스트라 구현 (동작 과정)

다익스트라 알고리즘은 다음 6가지 단계를 거쳐 동작합니다.

  1. 우선순위 큐에 시작 노드 추가: 시작점의 비용을 0으로 설정하고 큐에 삽입합니다.
  2. 우선순위가 가장 높은 노드 추출: 큐에서 누적 비용이 가장 적은 노드를 꺼냅니다.
  3. 방문 여부 확인: 이미 처리된(더 짧은 경로로 방문한 적이 있는) 노드라면 무시합니다.
  4. 비용 업데이트: 처음 방문하는 노드라면 현재까지의 비용을 최단 비용으로 기록합니다.
  5. 현재 노드와 연결된 노드를 우선순위 큐에 추가: 인접한 노드들로 가는 새로운 누적 비용을 계산하여 큐에 넣습니다.
  6. 반복 및 반환: 큐가 빌 때까지 위 과정을 반복하고, 목적지에 기록된 비용을 반환합니다.

4. 파이썬(Python) 구현 예시

그래프의 정점들이 1부터 N까지 연속된 정수라면 배열(리스트)을 사용하는 것이 일반적이지만, 정점의 이름이 문자열이거나 불연속적인 숫자라면 **딕셔너리(Dictionary)**를 활용하는 것이 훨씬 유연하고 파이썬다운 구현 방식입니다.

비가중치 그래프 vs 가중치 그래프의 딕셔너리 표현법

# 비가중치 그래프의 표현법 (도착 노드만 저장)
unweighted_graph = {
    1: [2, 4],
    2: [3, 5, 6],
    3: [6],
    4: [3, 7],
    5: [8],
    6: [5],
    7: [6, 8],
    8: []
}
 
# 가중치 그래프의 표현법 (비용과 도착 노드를 함께 저장)
weighted_graph = {
    1: [(2, 2), (4, 1)],      # 1에서 2로 가는 비용 2, 1에서 4로 가는 비용 1
    2: [(3, 3), (5, 1), (6, 5)],
    3: [(6, 4)],
    4: [(3, 2), (7, 5)],
    5: [(8, 1)],
    6: [(5, 2)],
    7: [(6, 1), (8, 3)],
    8: []
}

딕셔너리를 활용한 다익스트라 구현

위에서 설명한 6단계 과정을 딕셔너리와 heapq를 사용하여 깔끔하게 구현한 코드입니다. 이 방식은 방문 배열(visited)과 최단 거리 배열(distances)을 하나의 costs 딕셔너리로 통합하여 관리할 수 있다는 큰 장점이 있습니다.

import heapq
 
def dijkstra(graph, start, final):
    # 각 노드까지 도달하는 데 얼만큼의 최소 비용이 들었는지를 매핑할 딕셔너리
    costs = {}
    
    # 우선순위 큐 (Priority Queue)
    pq = []
    
    # 1. 우선순위 큐에 시작 노드 추가 (비용 0, 시작 노드)
    # Heap을 이용함
    heapq.heappush(pq, (0, start))
    
    while pq:
        # 2. 우선순위가 가장 높은(가장 적은 비용의) 노드 추출
        cur_cost, cur_v = heapq.heappop(pq)
        
        # 3. 방문 여부 확인 (costs 딕셔너리에 없다면 처음 방문하는 최단 경로임)
        if cur_v not in costs:
            # 4. 비용 업데이트
            costs[cur_v] = cur_cost
            
            # 목적지에 도달했다면 일찍 종료할 수도 있음 (선택 사항)
            if cur_v == final:
                break
                
            # 5. 현재 노드와 연결된 노드를 우선순위 큐에 추가
            # graph[cur_v]의 원소가 (간선 비용, 도착 노드) 형태라고 가정
            for edge_cost, next_v in graph.get(cur_v, []):
                next_cost = cur_cost + edge_cost # 누적 비용을 계산한 뒤
                heapq.heappush(pq, (next_cost, next_v)) # 우선순위 큐에 적재
                
    # 6. 목적지에 기록된 비용 반환
    # 도달할 수 없는 경우를 대비해 get() 메서드 사용 (없으면 무한대 반환)
    return costs.get(final, float('inf'))
 
# 실행 예시
start_node = 1
final_node = 8
min_cost = dijkstra(weighted_graph, start_node, final_node)
print(f"{start_node}에서 {final_node}까지의 최소 비용: {min_cost}")

5. 시간 복잡도

  • 시간 복잡도: 또는 (V는 정점의 개수, E는 간선의 개수)
    • 우선순위 큐(최소 힙)를 사용했기 때문에 얻을 수 있는 매우 빠른 성능입니다.
    • 최대 간선의 개수()만큼 우선순위 큐에 원소가 들어가고 빠질 수 있으며, 힙의 삽입/삭제 연산은 입니다. 그래프 구조상 이므로 는 와 같습니다.

요약

  • 가중치가 없는 그래프의 최단 경로: BFS
  • 가중치가 있는(양수) 그래프의 최단 경로: 다익스트라(Dijkstra) 알고리즘
  • 구현 핵심: **최소 힙(Priority Queue)**을 사용하여 매 순간 가장 가까운 노드를 뽑는다. 특히, **딕셔너리(costs)**를 활용하면 배열 크기를 미리 지정할 필요 없이 더 유연하고 파이썬다운 코드를 작성할 수 있습니다.

연관된 문제들:

면접 질문:

  1. 일반적인 Queue(큐)와 Priority Queue(우선순위 큐)의 가장 큰 차이점은 무엇인가요?

  2. 우선순위 큐를 다양한 방식으로 구현할 때, 삽입(Enqueue)과 삭제(Dequeue) 연산 모두 평균적으로 O(log n)의 시간 복잡도를 제공하여 가장 효율적인 것으로 알려진 자료구조는 무엇일까요?

  3. Min-Heap(최소 힙)에서 부모 노드와 자식 노드 값들 사이에는 어떤 관계가 성립하나요?

  4. 가중치가 있는 그래프에서 특정 시작 노드로부터 다른 모든 노드까지의 최단 경로를 찾기 위해 사용되는 대표적인 알고리즘은 무엇인가요?

  5. Dijkstra 알고리즘 구현 시 우선순위 큐(힙)를 사용하는 핵심적인 이유는 무엇인가요?

Graph View