Algorithm Guidecomplexity: O(E log V)

다익스트라 (Dijkstra)

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

01 Explore How It Works

Interactive Step-by-Step

HOVER OR SCROLL

Dijkstra Shortest Path

Dijkstra 시작. 시작 노드 A의 거리를 0, 나머지는 ∞로 두고 우선순위 큐에 A를 넣습니다.

Logic Node1 / 13

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

02 Understand It Simply

For Everyone

🔑Analogy

출발지에서 가까운 곳부터 하나씩 확정해 나가는 내비게이션 길찾기.

💡In Plain Words

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

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

📍Where It's Used

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

03 Python Implementation

A clean, readable reference implementation of the core logic of 다익스트라 (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