한양과기고 에듀테크 수업도구 대시보드

다익스트라 최단 경로 (Dijkstra's Algorithm)

간선마다 비용(가중치)이 다른 그래프에서 한 출발점으로부터 모든 곳까지의 최소 비용을 구하는 알고리즘이다. 핵심은 탐욕적 확정 — 아직 확정되지 않은 노드 중 현재까지 거리가 가장 짧은 노드를 우선순위 큐에서 꺼내 "이 값이 최종값"으로 못 박고(확정), 그 이웃들의 거리를 완화(relax)한다. 한 번 확정된 노드는 다시 보지 않으므로, 음수 간선이 없을 때만 정답을 보장한다. 아래 격자에서 숫자는 그 칸에 들어가는 비용이다. BFS는 칸 수만 세지만, 다익스트라는 비용의 합을 최소화한다.

가중 격자 길 찾기 시뮬레이터

가중치 무시 (BFS처럼 칸 수만) 속도

칸을 클릭하면 벽이 되고, S(초록)·E(빨강) 태그를 드래그하듯 클릭해 출발/도착을 옮길 수 있어요 — S를 먼저 클릭한 뒤 빈 칸을 클릭하면 출발점이 이동합니다.

비용 1~2 (평지) 비용 3~5 (언덕) 비용 6~9 (험지) 벽 큐 대기(frontier) 확정(visited) 최단 경로

실행을 눌러 출발점(S)에서 도착점(E)까지 최소 비용 경로를 찾아보세요.

확정된 칸 수

최단 거리 (비용 합)

–

경로 길이 (칸 수)

–

핵심 코드 (heapq 우선순위 큐)

import heapq

def dijkstra(graph, start):           # graph[u] = [(v, weight), ...]
    dist = {start: 0}
    pq = [(0, start)]              # (지금까지 거리, 노드)
    while pq:
        d, u = heapq.heappop(pq)     # 거리가 가장 짧은 노드를 꺼내 확정
        if d > dist.get(u, float('inf')):
            continue                  # 이미 더 짧은 경로로 확정된 낡은 항목
        for v, w in graph[u]:
            nd = d + w
            if nd < dist.get(v, float('inf')):
                dist[v] = nd          # 완화(relax): 더 짧은 길 발견
                heapq.heappush(pq, (nd, v))
    return dist

왜 탐욕이 맞나? 가중치가 모두 0 이상이면, 큐에서 가장 작은 거리로 꺼낸 노드는 더 짧아질 여지가 없다 — 다른 어떤 경로도 이미 그만큼은 비용을 썼기 때문.
음수 간선이 있으면 이 가정이 깨진다 → 벨만-포드나 SPFA를 써야 한다.
우선순위 큐 덕분에 매번 최소값을 O(log V)에 찾아, 전체 O((V+E) log V).
도착점 하나만 필요하면 u == goal일 때 즉시 종료해도 된다. 여기에 휴리스틱을 더하면 A*가 된다.

BFS와 무엇이 다른가 · 어디에 쓰나

구분	BFS	다익스트라
간선 비용	모두 동일(1)	서로 다름 (≥ 0)
자료구조	일반 큐 (FIFO)	우선순위 큐 (최소 힙)
최적 기준	간선(칸) 개수 최소	비용 합 최소
시간복잡도	O(V+E)	O((V+E) log V)

내비게이션·지도: 도로마다 소요 시간이 다르므로 "가장 빠른 길"은 다익스트라(실무는 A*·Contraction Hierarchies로 가속).
네트워크 라우팅: OSPF 프로토콜이 링크 비용으로 라우터 간 최단 경로 트리를 계산한다.
게임 AI: 지형별 이동 코스트(늪·모래)를 반영한 유닛 경로 탐색.
일반화: "가장 신뢰도 높은 경로", "환승 최소 경로" 등 비용을 바꿔 끼우면 그대로 적용된다.