Algorithm Guidecomplexity: O(E log V)

다익스트라 (Dijkstra)

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

01 알고리즘 작동 원리 탐색

Interactive Step-by-Step

TAP OR HOVER

Dijkstra Shortest Path

시작A

현재—

거리 d—

상태대기

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 파이썬 구현 코드

다익스트라 (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

Guide Progress0%