다익스트라 알고리즘 (Dijkstra's Algorithm)

구현 코드 예시

import heapq

INF = float('inf')

def dijkstra(graph, start, n):
    """graph[v] = [(다음 정점, 비용), ...] 형태의 인접 리스트."""
    dist = [INF] * (n + 1)
    dist[start] = 0
    pq = [(0, start)]                 # (거리, 정점) — 거리가 앞에 와야 거리 기준으로 정렬된다

    while pq:
        d, v = heapq.heappop(pq)

        if d > dist[v]:               # 이미 더 짧은 경로로 처리한 정점이면 버린다
            continue

        for nxt, w in graph[v]:
            nd = d + w
            if nd < dist[nxt]:        # 더 짧아질 때만 갱신하고 큐에 넣는다
                dist[nxt] = nd
                heapq.heappush(pq, (nd, nxt))

    return dist

if d > dist[v]: continue 두 줄이 이 구현의 핵심이다. 힙에서 원소를 빼는 기능이 없어서 갱신할 때마다 새 항목을 밀어 넣는데, 그러다 보면 같은 정점이 여러 번 들어간다. 꺼낼 때 "이 값이 지금 기록보다 크면 낡은 정보"라고 판단해 건너뛰는 것이다. 이 검사를 빼도 답은 맞지만 불필요한 순회가 늘어 느려진다.

경로 자체가 필요하면 이전 정점을 기록해두고 거꾸로 따라가면 된다.

def dijkstra_with_path(graph, start, end, n):
    dist = [INF] * (n + 1)
    prev = [0] * (n + 1)              # 어디서 왔는지 기록
    dist[start] = 0
    pq = [(0, start)]

    while pq:
        d, v = heapq.heappop(pq)
        if d > dist[v]:
            continue
        for nxt, w in graph[v]:
            if d + w < dist[nxt]:
                dist[nxt] = d + w
                prev[nxt] = v
                heapq.heappush(pq, (d + w, nxt))

    path, cur = [], end               # 끝에서부터 거슬러 올라간다
    while cur != start:
        path.append(cur)
        cur = prev[cur]
    path.append(start)
    return dist[end], path[::-1]

어떤 알고리즘을 쓸 것인가

자주 하는 실수

• 힙에 (정점, 거리) 순으로 넣는다. 파이썬 힙은 튜플의 첫 원소로 비교하므로 거리가 앞이어야 한다. 순서를 바꾸면 정점 번호가 작은 것부터 꺼내져서 완전히 다른 알고리즘이 된다.
• 방문 배열을 따로 만들어 관리한다. visited를 두는 대신 d > dist[v]로 걸러내는 편이 간결하고 실수가 적다. 굳이 둔다면 꺼낼 때 표시해야 하며, 넣을 때 표시하면 갱신 기회를 놓친다.
• 거리 초기값을 0이나 작은 수로 둔다. 반드시 충분히 큰 값이어야 한다. float('inf')나 문제 제약을 넘는 큰 정수를 쓴다.
• 음수 간선에 그대로 쓴다. 오류 없이 조용히 틀린 답이 나온다. 문제에 음수 비용이 있는지 먼저 확인한다.
• 무방향 그래프에서 한 방향만 넣는다. 양쪽 모두 graph[a].append((b, w)), graph[b].append((a, w))로 넣어야 한다.
• 도달 불가 정점을 처리하지 않는다. 결과에 INF가 남아 있으면 "도달 불가"라는 뜻이다. 그대로 출력하면 이상한 값이 찍힌다.

면접에서 이렇게 물어본다

• 다익스트라가 탐욕 알고리즘인 이유를 설명해 보라.
• 음수 간선이 있으면 왜 동작하지 않는지 반례를 들어 설명해 보라.
• 우선순위 큐를 쓰면 복잡도가 어떻게 개선되는가.
• 힙에서 낡은 항목을 걸러내는 방법과 그것이 필요한 이유는 무엇인가.
• BFS로 최단 거리를 구할 수 있는 조건은 무엇인가.
• 벨만-포드, 플로이드-워셜과 다익스트라를 어떤 기준으로 선택하겠는가.
• 최단 거리뿐 아니라 실제 경로를 구하려면 무엇을 추가해야 하는가.