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

다익스트라(Dijkstra) 알고리즘은 다이나믹 프래그래밍을 활용한 대표적인 최단 경로(Shortest Path)탐색 알고리즘이다. 흔히 인공위성 GPS 소프트웨어 등에서 가장 많이 사용된다. 다익스트라 알고리즘은 특정한 하나의 정점에서 다른 모든 정점으로 가든 최단 경로를 알려준다. 하지만 이 때, 음의 간선을 포함할 수 없다. 물론 현실 세계에서는 음의 간선이 존재하지 않기 때문에 다익스트라 알고리즘은 현실 세게에 사용하기 매우 적합한 알고리즘 중 하나라 할 수 있다.

다익스트라 알고리즘이 다이나믹 프로그래밍(DP) 문제인 이유는 '최단 거리는 여러 개의 최단 거리로 이루어져있기 때문이다' 작은 문제가 큰 문제의 부분집합에 속해있다고 볼 수 있다. 기본적으로 다익스트라는 하나의 최단 거리를 구할 때, 그 이전까지 구했던 최단 거리 정보를 그대로 사용한다는 특징이 있다.

동작 원리

1. 출발 노드와 도착 노드를 설정한다
2. 최단 거리 테이블을 초기화 한다.
3. 현재 위치한 노드의 인접 노드 중 거리가 가장 짧은 노드를 선택한다.
4. 해당 노드를 거쳐 다른 노드로 넘어가는 간선 비용(가중치)을 게산해 '최단 거리 테이블'을 업데이트 한다.
5. 3~4번 과정을 반복한다.

'최단 거리 테이블'은 1차원 배열로, N개 노드까지 오는 데 필요한 최단 거리를 기록한다. N개 크기의 배열을 선언하고 큰 값을 넣어 초기화한다.

시간 복잡도

간선의 수를 E, 정점의 수를 V라 했을 때 O(ElogV)가 된다.
최소힙을 이용하여 연결된 노드만 탐색하기 때문에 최악의 경우라도 총 간선 수인 E만큼만 반복하다.

예시

백준 1916 최소비용 구하기

import sys
import heapq

input = sys.stdin.readline

# 도시 개수 N, 버스개수 M
N = int(input())
M = int(input())
distance =[sys.maxsize]*(N+1)
l =[[]for _ in range(N+1)]
# a 출발 도시 번호, b 도착 도시 번호, c 버스 비용
for _ in range(M):
    a,b,c = map(int,input().split())
    l[a].append((b,c))

# x 출발지, y 목적지
x,y = map(int,input().split())
temp = []
def dijkstra(start):
    heapq.heappush(temp,start)
    distance[start[0]] = 0
    while temp:
        current, dist = heapq.heappop(temp)
        if distance[current] < dist : continue
        
        for i in l[current]:
            next, nextdist = i[0],dist + i[1]
            if distance[next] > nextdist:
                distance[next] = nextdist
                heapq.heappush(temp,(next,nextdist))
        
dijkstra((x,0))

print(distance[y])