다익스트라(Dijkstra) 알고리즘
- 다이나믹 프로그래밍을 활용한 대표적인 최단 경로 탐색 알고리즘
- 기본적으로 그리디 알고리즘으로 분류됨
- 특정한 하나의 정점에서 다른 모든 정점으로 가는 최단 경로를 알려준다.
- 다만 음의 간선은 포함할 수 없음
- 따라서 현실 세계에 사용하기 매우 적합한 알고리즘 중 하나
- 다이나믹 프로그래밍인 이유
- 최단 거리는 여러 개의 최단 거리로 이루어져있기 때문
- 작은 문제가 큰 문제의 부분 집합에 속해있다고 볼 수 있다.
- 하나의 최단 거리를 구할 때 그 이전까지 구했던 최단 거리 정보를 그대로 사용
동작
- 출발 노드와 도착 노드 설정
- 최단 거리 테이블 초기화
- 현재 위치한 노드의 인접 노드 중 방문하지 않은 노드를 구별 후 가장 짧은 노드 선택 및 방문
- 해당 노드를 거쳐 다른 노드로 넘어가는 간선 비용(가중치)을 계산하여 ‘최단 거리 테이블’ 업데이트
- 1~4 반복
구현
1. 순차 탐색
- 방문하지 않은 노드 중 가장 가까운 노드를 다음 탐색 노드로
- 그 탐색 과정이 순차 탐색으로 구현됨
- 노드의 개수만큼 수행
- O(N2)
import sys
input = sys.stdin.readline
INF = int(1e9)
n, m = map(int, input().split())
start = int(input())
graph = [[] for i in range(n+1)]
visited = [False] * (n + 1)
distance [INF] * (n + 1)
for _ in range(m):
a, b, c = map(int, input().split())
graph[a].append((b, c))
def get_smallest_node():
min_value = INF
index = 0
for i in range(1, n+1):
if distance[i] < min_value and not visited[i]:
min_value = distance[i]
index = i
return index
def dijkstra(start):
dijkstra[start] = 0
visited[start] = True
for j in graph[start]:
distance[j[0]] = j[1]
for i in range(n - 1):
now = get_smallest_node()
visited[now] = True
for j in graph[now]:
cost = distance[now] + j[1]
if cost < distance[j[0]]:
distance[j[0]] = cost
dijkstra(start)
for i in range(1, n+1):
if distance[i] == INF:
print('INFINITY')
else:
print(distance[i])
2. 우선순위 큐
- 거리 값을 담을 우선순위 큐는 힙으로 구현하고, 최소 힙으로 구현한다면 매번 루트 노드가 최소 거리를 갖는 노드가 됨
- 우선순위가 가장 높은 데이터를 가장 먼저 삭제한다는 점이 특징
- 현재 가장 가까운 노드를 저장하기 위한 목적으로만 우선순위 큐를 추가로 이용
- heapq 라이브러리 사용
- ‘우선순위’ = 가장 가까운 노드
- 방문여부 기록 안해도 된다는 점이 순차 탐색과 다름
- <거리, 노드>로 담는다.
- O(ElogV)
import heapq
import sys
input = sys.stdin.readline
INF = int(1e9)
n, m = map(int, input().split())
start = int(input())
graph = [[] for i in range(n + 1)]
distance = [INF] * (n + 1)
for _ in range(m):
a, b, c = map(int, input().split())
graph[a].append((b, c))
def dijkstra(start):
q = []
haepq.heappush(q, (0, start))
distance[start] = 0
while q:
dist, now = heapq.heappop(q)
if distance[now] < dist:
continue
for i in graph[now]:
cost = dist + i[1]
if cost < distance[i[0]]:
distance[i[0]] = cost
heapq.heappush(q, (cost, i[0]))
dijkstra(start)
for i in range(1, n+1):
if distance[i] == INF:
print('INFINITY')
else:
print(distance[i])
백준 문제 풀이
18352 특정 거리의 도시 찾기
import heapq
import sys
input = sys.stdin.readline
INF = int(1e9)
n, m, k, x = map(int, input().split())
graph = [[] for _ in range(n+1)]
distance = [INF] * (n+1)
for _ in range(m):
a, b = map(int, input().split())
graph[a].append(b, c)
def dijkstra(start):
q = []
heapq.heappush(q, (0, start))
distance[start] = 0
while q:
dist, now = heapq.heappop(q)
if distance[now] < dist:
continue
for i in graph[now]:
cost = dist + i[1]
if cost < distance[i[0]]:
distance[i[0]] = cost
heapq.heappush(q, (cost, i[0]))
dijkstra(x)
answer = []
for i in range(1, n+1):
if distance[i] == k:
answer.append(i)
if len(answer) == 0:
print(-1)
else:
for i in answer:
print(i, end='\n')
1446 지름길
import heapq
import sys
input = sys.stdin.readline
INF = int(1e9)
def dijkstra(start):
q = []
heapq.heappush(q,(0,start))
distance[start] = 0
while q:
dist, now = heapq.heappop(q)
if dist > distance[now]:
continue
for i in graph[now]:
cost = dist + i[1]
if cost < distance[i[0]]:
distance[i[0]] = cost
heapq.heappush(q,(cost, i[0]))
n , d = map(int,input().split())
graph = [[] for _ in range(d+1)]
distance = [INF] * (d+1)
for i in range(d):
graph[i].append((i+1, 1))
for _ in range(n):
s, e, l = map(int,input().split())
if e > d:
continue
graph[s].append((e,l))
dijkstra(0)
print(distance[d])
1916 최소비용 구하기
import heapq
import sys
input = sys.stdin.readline
INF = int(1e9)
def dijkstra(start):
q = []
heapq.heappush(q,(0,start))
distance[start] = 0
while q:
dist, now = heapq.heappop(q)
if dist > distance[now]:
continue
for i in graph[now]:
cost = dist + i[1]
if cost < distance[i[0]]:
distance[i[0]] = cost
heapq.heappush(q,(cost, i[0]))
n, m = map(int, input().split())
graph = [[] for _ in range(n+1)]
distance = [INF] * (n+1)
for _ in range(m):
a, b, w = map(int, input().split())
graph[a].append((b, w))
s, e = map(int, input().split())
dijkstra(s)
print(distance[e])
5972 택배 배송
import heapq
import sys
input = sys.stdin.readline
INF = int(1e9)
def dijkstra(start):
q = []
heapq.heappush(q,(0,start))
distance[start] = 0
while q:
dist, now = heapq.heappop(q)
if dist > distance[now]:
continue
for i in graph[now]:
cost = dist + i[1]
if cost < distance[i[0]]:
distance[i[0]] = cost
heapq.heappush(q,(cost, i[0]))
n, m = map(int, input().split())
graph = [[] for _ in range(n + 1)]
distance = [INF] * (n+1)
for _ in range(m):
a,b,c = map(int, input().split())
graph[a].append((b, c))
graph[b].append((a, c))
dijkstra(1)
print(distance[-1])
13549 숨바꼭질 3
import sys
from heapq import heappush, heappop
input = sys.stdin.readline
inf = sys.maxsize
n, k = map(int, input().split())
dp = [inf] * (100001)
heap = []
def dijkstra(n, k):
if k <= n:
print(n - k)
return
heappush(heap, [0, n])
while heap:
w, n = heappop(heap)
for nx in [n + 1, n - 1, n * 2]:
if 0 <= nx <= 100000:
if nx == n * 2 and dp[nx] == inf:
dp[nx] = w
heappush(heap, [w, nx])
elif dp[nx] == inf:
dp[nx] = w + 1
heappush(heap, [w + 1, nx])
print(dp[k])
dijkstra(n, k)
17396 백도어
import heapq
import sys
input = sys.stdin.readline
INF = int(1e9)
def dijkstra(start):
q = []
heapq.heappush(q, (0, start))
dis[start] = 0
while q:
d, now = heapq.heappop(q)
if dis[now] < d:
continue
for v, w in graph[now]:
cost = d + w
if cost < dis[v] and check[v] == 0:
dis[v] = cost
heapq.heappush(q, (cost, v))
N, M = map(int, input().split())
graph = [[] for _ in range(N+1)]
dis = [INF]*(N+1)
check = list(map(int, input().split()))
check[-1] = 0
for _ in range(M):
a, b, t = map(int, input().split())
graph[a].append((b, t))
graph[b].append((a, t))
dijkstra(0)
print(dis[N-1] if dis[N-1] != INF else -1)
