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

다익스트라 알고리즘은 하나의 정점에서 출발해 다른 모든 정점까지의 최단거리를 구하는 알고리즘이다. 대표적인 그리디 알고리즘 중 하나다. 모든 간선의 가중치가 0 이상의 양수일 때 사용할 수 있다.

🧠 과정

d 리스트에는 출발점으로부터 각 노드까지의 최단 거리가 저장된다.

1. 모든 노드의 거리를 무한대(inf)로 초기화하고, 시작 노드의 인덱스(노드 번호와 동일)의 값만 0으로 설정한다.
2. 이후 아직 방문하지 않은 노드들 중에서, 현재 최단거리가 가장 짧은(=출발점으로부터 가장 가까운, d에 들어가있는 값이 가장 작은) 노드 A를 선택한다.
3. 노드 A와 연결된 모든 노드 B에 대해, d[A] + (A와 B 사이의 거리) 가 d[B]보다 작으면, d[B]를 해당 값으로 갱신한다.
4. 모든 B에 대해 이 작업을 마치면 A를 방문 완료 상태로 바꾼다.
5. 그다음 다시 아직 방문하지 않은 노드들 중에서 최단 거리가 가장 짧은 노드를 골라서 앞의 과정을 반복한다.
6. 모든 노드가 방문 완료 상태가 되면 알고리즘을 종료한다.

---

작성 코드

문제: 백준 1753. 최단경로

import sys
import heapq
input = sys.stdin.readline

V, E = map(int, input().split())
K = int(input())

d = [float('inf') for _ in range(V+1)]  # 인덱스가 노드 번호
d[K] = 0  # 시작 노드의 거리 초기화

# 각 노드와 연결되는 간선 정보 저장
edges = {}
for i in range(1, V+1):
    edges[i] = []  
for _ in range(E):
    u, v, w = map(int, input().split())
    edges[u].append((v, w))

pq = []  # 우선순위 큐: [거리, 노드번호] 형태로 저장. 가장 작은 거리의 노드 번호를 반환하도록
heapq.heappush(pq, [0, K])

while pq:
    dist, start = heapq.heappop(pq)  # 출발점으로부터 가장 작은 거리, 노드번호를 pop
    if d[start] < dist:  # 이미 방문한 노드인 경우 스킵
        continue

    for edge in edges[start]:  # start 노드와 연결된 간선에 대한 정보
        end = edge[0]
        weight = edge[1]
        # start 노드에서 end 노드로 가는 거리 갱신
        if d[start] + weight < d[end]:
            d[end] = d[start] + weight
            # 갱신된 거리와 노드번호를 우선순위 큐에 넣음
            heapq.heappush(pq, [d[end], end])

# 결과 출력
for i in range(1, len(d)):
    if d[i] == float('inf'):
        print("INF")
    else:
        print(d[i])

이 문제에서는 노드의 개수가 최대 20000개였기 때문에, 메모리 초과 방지를 위해 인접행렬 대신 인접리스트를 사용했다.

---

💡 풀이: 우선순위 큐(Priority Queue) 사용하기

다익스트라 알고리즘에서 우선순위 큐를 쓰면 훨씬 빨라진다. 최단 거리가 가장 짧은 노드를 효율적으로 선택할 수 있기 때문이다.
단순히 리스트를 순회해서 최단 거리 노드를 찾으면 노드 한 개를 처리하는 데 O(V)가 걸리고, 이걸 모든 노드(V)에 대해 반복하면 최종 시간 복잡도는 O(V^2)가 된다.
하지만 우선순위 큐를 쓰면 최단 거리 노드를 O(log V)시간에 꺼낼 수 있다. 모든 간선(E개)에 대해 최소 한 번씩은 큐 연산이 발생하므로, 전체 시간 복잡도는 O(E log V)로 줄어든다.

d[A] + (A와 B 사이의 거리)가 d[B]보다 작을 때마다, 큐에 [새롭게 갱신된 d[B], B] 형태로 넣는다. 즉, 시작점부터 해당 노드까지의 [최단거리, 노드번호] 형태로 넣어서, 거리값이 가장 작은 노드가 pop되도록 구성한다.

🤔 의문

여기서 처음에 이런 의문이 들었다(나만ㅎ).

[최단거리, 노드번호] 형태로 큐에 넣는데, 같은 노드번호 B에 대해 최단거리인 d[B]가 계속 갱신되는 상황이다. 그럼 결국 pq에 들어있는 원하는 노드번호를 가진 요소를 찾아서 그 요소의 최단거리값을 직접 수정해줘야만 하는 상황 아닌가? 그런데 우선순위 큐에서 임의의 요소를 찾거나 수정하려고 하는 순간 시간이 O(V)로 늘어나버리는데? 그럼 우선순위 큐의 장점이 사라지는 거 아닌가?

그런데 기존 요소를 찾아서 갱신해줄 필요가 없었다!
단순히 새로운 거리값이 들어간 요소를 push해주기만 하면 되었다.

그래도 되는 이유는, 어차피 새롭게 들어가는 정보가 무조건 더 짧아서 먼저 pop되기 때문이다. 그리고 나중에 pop되는 오래된 정보는 이미 방문된 상태로 처리해서 무시하면 된다.
이렇게 하면 된다:

dist, start = heapq.heappop(pq)  # 출발점으로부터 가장 작은 거리, 노드번호를 pop
if d[start] < dist:  # 이미 방문한 노드인 경우 스킵
	continue

이 조건은, 현재 pop된 요소의 최단거리인 dist가 d[start]보다 크다면 이미 더 짧은 거리로 방문된 상태이므로 굳이 다시 처리하지 않겠다는 의미다.
이렇게 하면 우선순위 큐 내부 값을 직접 수정할 필요 없이 자연스럽게 최신 정보만 반영할 수 있게 된다.

🧩 visited 배열을 쓴다면?

근데 d[start] < dist 대신에, visited 배열을 따로 둬서 관리하는 게 코드는 길어져도 가독성은 더 좋지 않나 싶기도 하다.
뭐가 더 좋을까? 챗지피티한테 물어봤다.

🔥 삐티의 판단

항목	visited[] 방식	d[now] < dist 방식
코드 길이	길어짐	짧고 깔끔
가독성	명확한 방문 체크	거리 비교로 방문 판단
성능 차이	거의 없음	거의 없음
추천	학습용/대회용	실전 구현/빠른 코딩

성능 차이는 거의 없다고 한다.
굳이 따지자면, 정점의 수가 아주 많을 경우 visited 배열을 쓴다면 메모리 사용량이나 메모리 접근 비용이 약간 증가할 수 있다. 하지만 이건 복잡도에 영향을 주지 않는 미세한 수준이니 그냥 상황에 따라 선택하면 될 것 같다.