다익스트라 알고리즘 정리 | BFS와 차이, 우선순위 큐 구현까지

최단거리 문제라고 해서 항상 BFS를 쓰는 것은 아니다.

BFS가 정확하게 동작하는 경우는 모든 간선의 가중치가 같을 때다. 이 경우에는 먼저 도달한 경로가 곧 최단거리이기 때문에, 레벨 순서대로 탐색하는 BFS가 자연스럽다. 반면 간선마다 비용이 다르면, 더 적은 횟수로 이동한 경로가 더 짧다는 보장이 사라진다. 이때 필요한 알고리즘이 다익스트라(Dijkstra) 다. 다익스트라는 음의 가중치가 없는 그래프에서, 하나의 시작점으로부터 다른 모든 정점까지의 최단거리를 구하는 대표 알고리즘이다.

즉, 다익스트라는 이렇게 이해하면 된다.

• BFS: 간선 비용이 전부 같을 때 최단거리
• 다익스트라: 간선 비용이 서로 다를 때 최단거리

이 글에서는 파이썬 기준으로, 왜 다익스트라가 필요한지, 어떤 방식으로 구현하는지, 코드에서 어디를 봐야 하는지만 정리한다.

---

왜 BFS로는 안 되는가

예를 들어 시작점에서 어떤 노드까지 가는 방법이 두 가지 있다고 하자.

• 한 번에 도달하는 경로의 비용: 5
• 두 번 거쳐서 도달하는 경로의 비용: 4

이 경우 BFS는 “먼저 도달한 경로”를 더 자연스럽게 처리하지만, 실제 최단거리는 두 번째 경로다.

즉, 짧은 step 수가 짧은 거리 자체를 보장하지 않는다는 것이 가중치 그래프의 핵심이다. 다익스트라는 이 문제를 해결하기 위해, 현재까지 알려진 거리값이 가장 작은 노드부터 선택해서 주변 노드의 거리값을 갱신한다. 이 과정은 보통 “방문하지 않은 노드 중 가장 비용이 적은 노드를 선택하고, 그 노드로부터 갈 수 있는 노드들의 비용을 갱신한다”로 설명된다.

---

다익스트라의 핵심 아이디어

다익스트라는 결국 아래 흐름으로 돌아간다.

1. 모든 노드까지의 거리를 무한대로 초기화한다.
2. 시작 노드의 거리를 0으로 둔다.
3. 현재까지 거리값이 가장 작은 노드를 고른다.
4. 그 노드를 거쳐 갈 수 있는 이웃 노드들의 거리 후보를 계산한다.
5. 기존 거리보다 더 짧으면 갱신한다.
6. 이를 반복한다.

이때 구현 방식은 크게 두 가지가 있다.

• 순차 탐색 방식: 매번 거리 테이블을 훑어서 가장 짧은 노드를 찾음
• 우선순위 큐 방식: 가장 짧은 노드를 더 빠르게 꺼냄

순차 탐색 방식은 보통 O(V^2)이고, 우선순위 큐를 쓰면 일반적으로 O((V+E) log V)까지 줄일 수 있다. 실전 코딩테스트에서는 대부분 우선순위 큐 방식으로 구현한다.

---

파이썬 구현

파이썬에서는 heapq를 사용한 우선순위 큐 구현이 가장 일반적이다.

import heapq

INF = int(1e9)

def dijkstra(start, graph, n):
    distance = [INF] * (n + 1)
    distance[start] = 0

    pq = []
    heapq.heappush(pq, (0, start))  # (현재까지 거리, 노드 번호)

    while pq:
        dist, now = heapq.heappop(pq)

        # 이미 더 짧은 거리로 처리된 적이 있으면 스킵
        if distance[now] < dist:
            continue

        for nxt, cost in graph[now]:
            new_cost = dist + cost

            if new_cost < distance[nxt]:
                distance[nxt] = new_cost
                heapq.heappush(pq, (new_cost, nxt))

    return distance

그래프는 보통 이렇게 만든다.

graph = [
    [],
    [(2, 2), (3, 5), (4, 1)],
    [(3, 3), (4, 2)],
    [(2, 3), (6, 5)],
    [(3, 3), (5, 1)],
    [(3, 1), (6, 2)],
    []
]

각 원소는 (다음 노드, 비용) 형태다.

즉, 인접 리스트를 쓰되 가중치까지 함께 저장하는 구조다. 우선순위 큐 방식에서도 그래프는 목적지와 거리 정보를 함께 저장하는 형태가 핵심이다.

---

코드에서 꼭 봐야 하는 부분

1. distance 배열은 “현재까지의 최단거리 후보표”다

distance = [INF] * (n + 1)
distance[start] = 0

처음엔 전부 무한대로 두고, 시작점만 0으로 둔다.

이 배열은 단순 방문 여부가 아니라, 각 노드까지 지금까지 알려진 최소 비용을 저장하는 테이블이다. 최단거리 알고리즘 설명에서도 확인되지 않은 값은 INF로 두고 시작하는 방식이 기본 전제로 등장한다.

2. 우선순위 큐에는 (거리, 노드)를 넣는다

heapq.heappush(pq, (0, start))

우선순위 큐는 “무엇을 기준으로 우선순위를 정할 것인지”가 중요하다.

다익스트라에서는 거리값이 가장 작은 노드를 먼저 꺼내야 하므로, 노드 번호만 넣는 것이 아니라 (거리, 노드) 형태로 넣어야 한다. 우선순위 큐 구현의 핵심도 결국 “거리가 짧은 노드를 우선 탐색”하는 데 있다.

3. 핵심은 방문 자체가 아니라 “갱신”이다

if new_cost < distance[nxt]:
    distance[nxt] = new_cost

다익스트라를 다익스트라답게 만드는 줄은 여기다.

BFS처럼 “방문 안 했으면 넣는다”가 아니라, 새로 계산한 비용이 기존 값보다 더 짧을 때만 갱신한다. 다익스트라 설명에서도 매 단계의 핵심은 “해당 노드로부터 갈 수 있는 노드들의 비용을 갱신한다”는 부분이다.

4. 오래된 후보는 버린다

if distance[now] < dist:
    continue

우선순위 큐 방식에서는 같은 노드가 여러 번 큐에 들어갈 수 있다.

나중에 더 짧은 경로가 발견되면 새 값이 다시 push되기 때문이다.

따라서 큐에서 꺼낸 (dist, now)가 이미 최신 최단거리보다 크면, 그건 오래된 정보이므로 건너뛴다. 우선순위 큐 구현에서도 중복 후보를 적절히 걸러주는 조건이 중요하다.

---

순차 탐색 방식과의 차이

다익스트라는 우선순위 큐 없이도 구현할 수 있다.

그 방식은 매번 distance 배열 전체를 훑어서, 방문하지 않은 노드 중 최솟값을 가진 노드를 직접 찾는 방식이다.

그 구조는 이해하기 쉽지만, 매 단계마다 전체를 다시 확인해야 하므로 비효율적이다. 그래서 노드 수와 간선 수가 커지는 문제에서는 우선순위 큐 방식이 훨씬 많이 쓰인다. 정리하면:

• 순차 탐색 구현: 개념 이해용
• 우선순위 큐 구현: 실전용

이 구분으로 보면 편하다. 순차 탐색 방식은 O(N^2), 우선순위 큐 방식은 O((V+E) log V)로 설명된다.

---

시간 복잡도

우선순위 큐를 사용하는 다익스트라의 시간 복잡도는 일반적으로 다음처럼 본다.

O((V + E) log V)

여기서

• V: 정점 수
• E: 간선 수

즉, 가중치가 있는 그래프에서 단일 시작점 최단거리를 구할 때 가장 자주 선택되는 기본 해법이라고 보면 된다.

---

정리

다익스트라는 “최단거리 알고리즘”이라는 말만 외우면 잘 안 남는다.

오히려 이렇게 기억하는 게 더 낫다.

가중치가 같으면 BFS를 먼저 보고, 가중치가 다르면 다익스트라를 본다.

이 기준이 잡히면 문제를 볼 때도 훨씬 빠르게 갈린다.

---

한 줄 정리

다익스트라는 가중치가 있는 그래프에서, 현재까지 가장 짧은 거리의 노드부터 선택해 거리 테이블을 갱신하는 최단거리 알고리즘이다.