다익스트라 (Dijkstra)

개념

가중치가 있는 그래프에서 한 정점에서 다른 모든 정점까지의 최단 경로를 구하는 알고리즘

그리디 방식으로 가장 가까운 정점을 선택하며 확장

---

시간복잡도

구현 방식	시간복잡도
인접 행렬 + 배열	O(V²)
인접 리스트 + 배열	O(V²)
인접 리스트 + 우선순위 큐	O((V + E) log V)
공간복잡도	O(V + E)

---

특징

장점

• 최단 경로 보장: 음수 가중치가 없으면 최적해
• 빠른 속도: 우선순위 큐 사용 시 O((V+E) log V)
• 단일 출발점: 한 번 실행으로 모든 정점까지 거리

단점

• 음수 가중치 불가: 음수 간선이 있으면 사용 불가
• 단일 출발점만: 모든 쌍 최단 경로는 불가 (플로이드-워셜 필요)

적용 조건

• 음수 가중치 없음: 모든 간선의 가중치 ≥ 0
• 방향/무방향 모두 가능

---

구현 방법

우선순위 큐 구현 (추천)

import heapq
 
def dijkstra(graph, start):
    """다익스트라 알고리즘 - 우선순위 큐"""
    n = len(graph)
    distances = [float('inf')] * n
    distances[start] = 0
 
    # 우선순위 큐: (거리, 정점)
    pq = [(0, start)]
 
    while pq:
        current_dist, current = heapq.heappop(pq)
 
        # 이미 처리된 정점
        if current_dist > distances[current]:
            continue
 
        # 인접 정점 탐색
        for neighbor, weight in graph[current]:
            distance = current_dist + weight
 
            # 더 짧은 경로 발견
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                heapq.heappush(pq, (distance, neighbor))
 
    return distances
 
# 테스트
# 그래프: graph[정점] = [(인접 정점, 가중치), ...]
graph = [
    [(1, 2), (2, 5)],           # 0번 정점
    [(0, 2), (2, 3), (3, 4)],   # 1번 정점
    [(0, 5), (1, 3), (3, 1)],   # 2번 정점
    [(1, 4), (2, 1)]            # 3번 정점
]
 
print(dijkstra(graph, 0))  # [0, 2, 5, 6]
 
# 시간복잡도: O((V + E) log V)
# 공간복잡도: O(V + E)

---

경로 추적 구현

import heapq
 
def dijkstra_with_path(graph, start, end):
    """경로까지 추적하는 다익스트라"""
    n = len(graph)
    distances = [float('inf')] * n
    distances[start] = 0
    previous = [-1] * n  # 이전 정점 기록
 
    pq = [(0, start)]
 
    while pq:
        current_dist, current = heapq.heappop(pq)
 
        if current_dist > distances[current]:
            continue
 
        # 목적지 도착
        if current == end:
            break
 
        for neighbor, weight in graph[current]:
            distance = current_dist + weight
 
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                previous[neighbor] = current
                heapq.heappush(pq, (distance, neighbor))
 
    # 경로 복원
    path = []
    current = end
    while current != -1:
        path.append(current)
        current = previous[current]
    path.reverse()
 
    return distances[end], path
 
# 테스트
graph = [
    [(1, 2), (2, 5)],
    [(0, 2), (2, 3), (3, 4)],
    [(0, 5), (1, 3), (3, 1)],
    [(1, 4), (2, 1)]
]
 
distance, path = dijkstra_with_path(graph, 0, 3)
print(f"최단 거리: {distance}")  # 6
print(f"경로: {path}")           # [0, 1, 2, 3]

---

배열 기반 구현 (밀집 그래프)

def dijkstra_array(graph, start):
    """배열 기반 다익스트라 (V² 복잡도)"""
    n = len(graph)
    distances = [float('inf')] * n
    distances[start] = 0
    visited = [False] * n
 
    for _ in range(n):
        # 미방문 정점 중 최소 거리 정점 찾기
        min_dist = float('inf')
        min_vertex = -1
 
        for v in range(n):
            if not visited[v] and distances[v] < min_dist:
                min_dist = distances[v]
                min_vertex = v
 
        if min_vertex == -1:
            break
 
        visited[min_vertex] = True
 
        # 인접 정점 갱신
        for neighbor in range(n):
            if graph[min_vertex][neighbor] != 0:
                weight = graph[min_vertex][neighbor]
                distance = distances[min_vertex] + weight
 
                if distance < distances[neighbor]:
                    distances[neighbor] = distance
 
    return distances
 
# 테스트 (인접 행렬)
# 0은 간선 없음을 의미
graph = [
    [0, 2, 5, 0],
    [2, 0, 3, 4],
    [5, 3, 0, 1],
    [0, 4, 1, 0]
]
 
print(dijkstra_array(graph, 0))  # [0, 2, 5, 6]
 
# 시간복잡도: O(V²)
# 밀집 그래프(간선 많음)에 효율적

---

동작 과정

그래프:
    0 --2-- 1
    |       |
    5       4
    |       |
    2 --3-- 3

시작: 0번 정점

1단계: distances = [0, ∞, ∞, ∞]
       0 선택, 인접: 1(거리 2), 2(거리 5)
       distances = [0, 2, 5, ∞]

2단계: distances = [0, 2, 5, ∞]
       1 선택, 인접: 3(거리 2+4=6)
       distances = [0, 2, 5, 6]

3단계: distances = [0, 2, 5, 6]
       2 선택, 인접: 3(거리 5+1=6, 갱신 안 함)
       distances = [0, 2, 5, 6]

4단계: distances = [0, 2, 5, 6]
       3 선택, 모든 정점 방문 완료

최종: [0, 2, 5, 6]

---

템플릿

import heapq
 
def dijkstra_template(graph, start):
    n = len(graph)
    distances = [float('inf')] * n
    distances[start] = 0
 
    pq = [(0, start)]
 
    while pq:
        current_dist, current = heapq.heappop(pq)
 
        # 이미 처리된 경우 스킵
        if current_dist > distances[current]:
            continue
 
        # 인접 정점 확인
        for neighbor, weight in graph[current]:
            distance = current_dist + weight
 
            # 최단 거리 갱신
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                heapq.heappush(pq, (distance, neighbor))
 
    return distances

---

최적화 기법

1. 방문 체크 (선택적)

def dijkstra_visited(graph, start):
    """방문 배열 사용"""
    n = len(graph)
    distances = [float('inf')] * n
    distances[start] = 0
    visited = [False] * n
 
    pq = [(0, start)]
 
    while pq:
        current_dist, current = heapq.heappop(pq)
 
        if visited[current]:
            continue
 
        visited[current] = True
 
        for neighbor, weight in graph[current]:
            if not visited[neighbor]:
                distance = current_dist + weight
 
                if distance < distances[neighbor]:
                    distances[neighbor] = distance
                    heapq.heappush(pq, (distance, neighbor))
 
    return distances

---

2. 조기 종료 (목적지만 찾기)

def dijkstra_early_exit(graph, start, end):
    """목적지 도착 시 종료"""
    n = len(graph)
    distances = [float('inf')] * n
    distances[start] = 0
 
    pq = [(0, start)]
 
    while pq:
        current_dist, current = heapq.heappop(pq)
 
        # 목적지 도착
        if current == end:
            return distances[end]
 
        if current_dist > distances[current]:
            continue
 
        for neighbor, weight in graph[current]:
            distance = current_dist + weight
 
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                heapq.heappush(pq, (distance, neighbor))
 
    return float('inf')  # 도달 불가

---

핵심 요약

개념	설명
원리	그리디 - 가장 가까운 정점 선택
시간복잡도	O((V+E) log V) - 우선순위 큐
공간복잡도	O(V + E)
적용 조건	음수 가중치 없음
활용	단일 출발점 최단 경로

---

다른 알고리즘과 비교

알고리즘	시간복잡도	음수 가중치	용도
다익스트라	O((V+E) log V)	불가	단일 출발점, 양수 가중치
벨만-포드	O(VE)	가능	단일 출발점, 음수 가중치
플로이드-워셜	O(V³)	가능	모든 쌍 최단 경로
BFS	O(V+E)	불가	가중치 없는 그래프

---

주의사항

1. 음수 가중치

# 음수 가중치가 있으면 작동 안 함
graph = [
    [(1, -5), (2, 3)],  # 음수 가중치!
    [(2, 2)],
    []
]
# 벨만-포드 알고리즘 사용 필요

2. 우선순위 큐 중복

# 같은 정점이 여러 번 큐에 들어갈 수 있음
# 거리 체크로 무시
if current_dist > distances[current]:
    continue  # 이미 처리됨

3. 초기화

# 시작 정점은 0으로 초기화
distances = [float('inf')] * n
distances[start] = 0  # 중요!

---

자주 나오는 문제 유형

1. 기본 최단 거리

문제: A에서 B까지 최단 거리

import heapq
 
def shortest_path(n, edges, start, end):
    """최단 거리 구하기"""
    graph = [[] for _ in range(n)]
 
    for u, v, w in edges:
        graph[u].append((v, w))
        # 무방향이면 양방향 추가
        # graph[v].append((u, w))
 
    distances = dijkstra(graph, start)
    return distances[end]
 
# 테스트
edges = [(0, 1, 2), (0, 2, 5), (1, 2, 3), (1, 3, 4), (2, 3, 1)]
print(shortest_path(4, edges, 0, 3))  # 6

---

2. 경유지를 거치는 최단 경로

문제: A → B → C 최단 경로

def shortest_path_via(graph, start, via, end):
    """경유지를 거치는 최단 경로"""
    # start → via
    dist1 = dijkstra(graph, start)
 
    # via → end
    dist2 = dijkstra(graph, via)
 
    total = dist1[via] + dist2[end]
 
    return total if total != float('inf') else -1
 
# 0 → 1 → 3 경로
graph = [
    [(1, 2), (2, 5)],
    [(2, 3), (3, 4)],
    [(3, 1)],
    []
]
 
print(shortest_path_via(graph, 0, 1, 3))  # 6

---

3. K번 이내 경유 최단 경로

문제: 최대 K개 정점을 거쳐 도달하는 최단 경로

import heapq
 
def shortest_path_k_stops(n, edges, start, end, k):
    """K번 이내 경유"""
    graph = [[] for _ in range(n)]
 
    for u, v, w in edges:
        graph[u].append((v, w))
 
    # (거리, 정점, 경유 횟수)
    pq = [(0, start, 0)]
    # distances[정점][경유 횟수]
    distances = [[float('inf')] * (k + 2) for _ in range(n)]
    distances[start][0] = 0
 
    while pq:
        current_dist, current, stops = heapq.heappop(pq)
 
        if current == end:
            return current_dist
 
        if stops > k:
            continue
 
        for neighbor, weight in graph[current]:
            distance = current_dist + weight
            new_stops = stops + 1
 
            if distance < distances[neighbor][new_stops]:
                distances[neighbor][new_stops] = distance
                heapq.heappush(pq, (distance, neighbor, new_stops))
 
    return -1
 
# 테스트
edges = [(0, 1, 100), (0, 2, 500), (1, 2, 100), (2, 3, 100)]
print(shortest_path_k_stops(4, edges, 0, 3, 1))  # 600

---

4. 양방향 최단 경로

문제: A → B 최단 거리 + B → A 최단 거리

def shortest_path_bidirectional(graph, reverse_graph, start, end):
    """양방향 최단 경로"""
    # 정방향
    dist_forward = dijkstra(graph, start)
 
    # 역방향
    dist_backward = dijkstra(reverse_graph, end)
 
    return dist_forward[end] + dist_backward[start]
 
# 방향 그래프
graph = [
    [(1, 2), (2, 5)],
    [(3, 4)],
    [(3, 1)],
    []
]
 
# 역방향 그래프 생성
reverse_graph = [[] for _ in range(4)]
for u in range(len(graph)):
    for v, w in graph[u]:
        reverse_graph[v].append((u, w))
 
print(shortest_path_bidirectional(graph, reverse_graph, 0, 3))

---

5. 최소 비용 경로 개수

문제: 최단 경로의 개수 세기

import heapq
 
def count_shortest_paths(graph, start, end):
    """최단 경로 개수"""
    n = len(graph)
    distances = [float('inf')] * n
    distances[start] = 0
    count = [0] * n
    count[start] = 1
 
    pq = [(0, start)]
 
    while pq:
        current_dist, current = heapq.heappop(pq)
 
        if current_dist > distances[current]:
            continue
 
        for neighbor, weight in graph[current]:
            distance = current_dist + weight
 
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                count[neighbor] = count[current]
                heapq.heappush(pq, (distance, neighbor))
            elif distance == distances[neighbor]:
                count[neighbor] += count[current]
 
    return distances[end], count[end]
 
# 테스트
graph = [
    [(1, 1), (2, 1)],
    [(3, 1)],
    [(3, 1)],
    []
]
 
distance, cnt = count_shortest_paths(graph, 0, 3)
print(f"최단 거리: {distance}, 경로 개수: {cnt}")  # 2, 2

---

추천 연습 문제

기초

• 백준 1753번 - 최단경로
• 백준 1916번 - 최소비용 구하기

중급

• 백준 1504번 - 특정한 최단 경로
• LeetCode 743 - Network Delay Time
• LeetCode 787 - Cheapest Flights Within K Stops

고급

• 백준 1238번 - 파티
• 백준 9370번 - 미확인 도착지

---

언제 사용할까?

사용 가능

• 양수 가중치: 모든 간선 가중치 ≥ 0
• 단일 출발점: 한 정점에서 다른 모든 정점
• 빠른 속도: O((V+E) log V)
• GPS, 네비게이션: 실제 활용 예시

사용 불가

• 음수 가중치: 벨만-포드 사용
• 모든 쌍 최단 경로: 플로이드-워셜 사용
• 가중치 없음: BFS가 더 빠름

결론: 음수 가중치가 없는 최단 경로 문제의 표준 알고리즘!