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

💡 기본 개념

• 최단 경로 알고리즘 중 하나
• 시작 정점에서 모든 정점까지의 최단 거리를 구하는 알고리즘이다.
• 방향그래프와 무방향그래프에서 사용할 수 있다.

 

💡 시간 복잡도

• V: 정점 수, E: 간선 수
• 단순 구현 : O(V²)
• 우선순위 큐 사용 : O((V + E) log V)
• 우선순위 큐를 사용하는 것이 더 효율적이기 때문에 대부분의 경우 우선순위 큐를 사용해서 구현한다.

 

💡 동작 과정

1. 방문하지 않은 정점 중 최단 거리가 가장 짧은 정점을 선택
2. 해당 정점을 기준으로 인접한 정점들의 거리를 확인하고 더 짧은 경로로 갱신
3. 모든 정점을 방문할 때까지 반복

 

✅ 동작 예시

다음과 같이 가중치가 있는 무방향 그래프에 대해 생각해보자.

   (0)
  /   \
 2     5
 /       \
(1)---1---(2)
   \
    9
     \
     (3)

 

실행 과정

단계	선택된 정점	배열 상태
0	-	[0, ∞, ∞, ∞]
1	0	[0, 2, 5, ∞]
2	1	[0, 2, 3, 11]
3	2	[0, 2, 3, 11]
4	3	[0, 2, 3, 11]

[0단계]

• 모든 정점까지의 거리를 무한대로 초기화.
• 시작 정점(0번)은 거리를 0으로 설정

[1단계]

• 선택된 정점: 0 (시작)
• 0번 정점에서 인접한 정점: 1번, 2번
• 정점1: 0에서 1로 가는 경로는 거리가 dist[0] + weight[0][1] = 2이기 때문에 dist[1]을 2로 갱신
• 정점2: 0에서 2로 가는 경로는 거리가 dist[0] + weight[0][2] = 5이기 때문에 dist[2]를 5로 갱신

[2단계]

• 선택된 정점: 1
  • 방문하지 않은 정점들 (1, 2, 3) 중에서 현재 dist 값이 가장 작은 정점 선택
• 1번 정점에서 인접한 정점: 0번, 2번, 3번
• 정점0: 이미 방문
• 정점2: 현재 dist[2]는 5. 1을 거쳐 2로 가는 새로운 경로는 dist[1] + weight[1][2] = 3 이기 때문에 dist[2]를 3으로 갱신
• 정점3: 1에서 3으로 가는 경로는 dist[1] + weight[1][3] = 11 이기 때문에 dist[3]를 11로 갱신

[3단계]

• 선택된 정점: 2
• 2번 정점에서 인접한 정점: 0번, 1번
• 모든 정점을 이미 방문했으므로 무시

[4단계]

• 선택된 정점: 3
• 3번 정점에서 인접한 정점: 1번
• 모든 정점을 이미 방문했으므로 무시

[최종 결과]

• dist: [0, 2, 3, 11]
• 0에서 3번까지의 최단거리는 11

 

💡 예시 코드

import heapq

def dijkstra(graph, start):
    V = len(graph)
    dist = [float('inf')] * V
    dist[start] = 0
    pq = [(0, start)]  # (거리, 정점)

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

        if d > dist[u]:
            continue

        for v, w in graph[u]:
            if dist[v] > dist[u] + w:
                dist[v] = dist[u] + w
                heapq.heappush(pq, (dist[v], v))

    return dist


# 그래프 (인접 리스트)
# graph[u] = [(v, w), ...] : u에서 v로 가중치 w
graph = [
    [(1, 2), (2, 5)],   # 0 → 1(2), 0 → 2(5)
    [(0, 2), (2, 1), (3, 9)],  # 1 → 0(2), 2(1), 3(9)
    [(0, 5), (1, 1)],   # 2 → 0(5), 1(1)
    [(1, 9)]            # 3 → 1(9)
]

print(dijkstra(graph, 0))  # 출력: [0, 2, 3, 11]

 

 

⚠️ 주의

음수 가중치가 있을 경우 올바르게 동작하지 않음 !!

 

 

💡 활용 사례

• 내비게이션 경로 탐색 (출발지 → 목적지)
• 네트워크 라우팅 (최소 비용 경로)
• 물류 배송 경로 최적화
• 게임 AI (맵 상 캐릭터 이동)