Algorithm Guidecomplexity: O(E log V)

다익스트라 (Dijkstra)

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

01 알고리즘 작동 원리 탐색

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 쉽게 이해하기

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