Algorithm Guidecomplexity: O(E log V)

다익스트라 (Dijkstra)

음수 간선이 없는 가중치 그래프에서 시작 노드로부터의 최단 거리를 구합니다. 우선순위 큐로 매번 거리가 가장 작은 노드를 확정하고 이웃을 완화(relax)하는 그리디 전략으로, 내비게이션·네트워크 라우팅의 표준입니다.

01다익스트라 (Dijkstra)

알고리즘 작동 원리 탐색

다익스트라를 시작합니다. 시작 노드 A까지의 거리는 0, 나머지는 아직 모르니 ∞로 둡니다.

지금까지 거리가 가장 짧은 A를 꺼내 확정합니다. 이웃 B·C로 가는 길을 재 봅니다.

A에서 B로 가면 6. 아직 아무 길도 없던 B에 6을 적어 둡니다.

A에서 C로 가면 1. C가 B보다 가까워 다음 확정 차례가 됩니다.

가장 가까운 C를 꺼내 확정합니다. C의 이웃 B·D로 가는 길을 재 봅니다.

C를 거쳐 B로 가면 3 — 곧장 가던 6보다 짧습니다. 더 짧은 길을 찾아 고쳐 씁니다.

C에서 D로 가면 6. 처음 재 보는 길이라 그대로 적습니다.

이제 가장 가까운 노드는 B입니다. 확정하고 D로 가는 길을 다시 재 봅니다.

B를 거쳐 D로 가면 4 — 앞서 적어 둔 6보다 짧아 고쳐 씁니다.

D를 확정하고 마지막 이웃 E로 가는 거리를 잽니다.

D에서 E까지 더하면 6. 마지막 노드의 거리도 정해졌습니다.

E를 꺼내 확정합니다. 더 살펴볼 노드가 없어 모든 최단 거리가 확정됐습니다.

완료 · A에서 E까지 최단 경로 A → C → B → D → E (거리 6). 강조된 간선이 최단 경로 트리입니다.

Live Python

1import heapq

2def dijkstra(graph, start):

# dist[A] = 0

3 dist = {start: 0}

4 pq = [(0, start)]

5 visited = set()

6 while pq:

7 d, u = heapq.heappop(pq)

8 if u in visited:

9 continue

10 visited.add(u)

11 for v, w in graph[u]:

12 nd = d + w

13 if nd < dist.get(v, INF):

14 dist[v] = nd

15 heapq.heappush(pq, (nd, v))

16 return dist

1 / 13

02 쉽게 이해하기

For Everyone

🔑핵심 동작

출발점에서 가장 가까운 정점부터 하나씩 최단 거리를 확정해 나갑니다. 음수 가중치가 있으면 이 확정이 깨집니다.

💡쉽게 말하면

우선순위 큐로 가장 가까운 노드를 하나씩 확정하며 최단 거리를 넓혀갑니다.

음수 간선이 없을 때 빠르고 정확해요.

📍어디에 쓰나

–내비게이션
–네트워크 라우팅
–최단 경로

03 파이썬 구현 코드

다익스트라 (Dijkstra)의 핵심 로직을 담은 표준 구현 예시입니다. 가급적 간결하고 읽기 쉬운 코드로 작성되었습니다.

core_implementation.py

import heapq

def dijkstra(graph, start):
    dist = {start: 0}
    pq = [(0, start)]
    visited = set()
    while pq:
        d, u = heapq.heappop(pq)
        if u in visited:
            continue
        visited.add(u)
        for v, w in graph[u]:
            nd = d + w
            if nd < dist.get(v, float("inf")):
                dist[v] = nd
                heapq.heappush(pq, (nd, v))
    return dist