개념
특징
- 최단 경로 알고리즘 중 가장 많이 사용된다.
- 무방향 그래프, 방향 그래프 모두 적용 가능하다.
- 모든 간선은 음이 아닌 비용을 가져야 한다.
- 시작 정점부터 모든 다른 정점까지의 최단 경로를 구하는 알고리즘
원리
- 시작 정점(v) 에서, 정점(u)까지의 최단경로 dist[u]를 구해, 정점 u가 집합 S에 추가되면, 새로 추가된 정점u 에 의해 단축되는 경로가 있는지를 체크한다.
- 현제 알고있는 dist[w]를 새로 추가된 정점 u를 거쳐서 가는 dist[u]+cost[u][w]와 비교, 경로가 단축된다면 dist[w]를 경로값으로 수정하면서 최단 경로를 찾는 알고리즘 이다.
dist[w] = min(dist[w], dist[u]+cost[u][w])
dijkstra(G, v)
S ← {v}
for i←0 to |V(G)|-1 do
dist[i] ← cost[v][i]
if cost[v][i] ≠ ∞ then
pred[i] ← v
else
pred[i] ← NULL
for(i←0; S!= V(G); i←i+1) do
u ← S에 속하지 않은 정점 중에서 dist[]가 최소인 정점
S ← S U {u}
for(w←0; w∈V(G); w←w+1) do
if(w∉S and dist[u]+cost[u][w]<dist[w]) then
dist[w] ← dist[u]+cost[u][w]
pred[w] ← u
end dijkstra()힙을 사용한 알고리즘
- Priority Queue (우선순위 큐) : 우선순위가 높은 데이터를 가장 먼저 삭제
- 파이썬에서 우선순위 큐가 필요할 경우
-
일반적으로 heapq 라이브러리 사용
-
Min Heap : 값이 낮은 데이터가 먼저 삭제
-
Max Heap : 값이 큰 데이터가 먼저 삭제 / heapq 라이브러리에서는 기본적으로 Min Heap 구조 사용
def dijkstra(start): q = [] # 시작노드로 가기 위한 최단 경로는 0으로 설정하며 힙에 삽입 heapq.heappush(q, (0, start)) distance[start] = 0 while q: # 힙이 비어 있지 않다면 # 가장 최단 거리가 짧은 노드 정보 꺼내기 dist, u = heapq.heappop(q) # 현재 노드가 이미 처리된 적 있는 노드라면 무시 if distance[u] < dist: continue # 현재 노드와 연결된 다른 인접 노드들 확인 for i in graph[u]: cost = dist + i[1] if cost < distance[i[0]]: # relaxation 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])
-
시간복잡도
- O(V^2)
- 힙 구조를 사용할경우 : O(VlogV)
필기
-
[참고] C++에서는 Max Heap, Java에서는 Min Heap으로 우선순위 라이브러리가 구현되어 있음
-
다익스트라 알고리즘은 DP를 활용한 대표적인 최단경로 탐색 알고리즘이다. 특정한 하나의 정점에서 다른 모든 정점으로 가는 최단 경로를 알아낼 수 있다. 현실 세계에서는 음의 간건이 존재하지 않기 때문에, 현실에 사용하기 매우 적합한 알고리즘중 하나라고 할 수 있다.
다익스트라 알고리즘이 DP문제인 이유는 ‘최단 거리는 여러개의 최단 거리로 이루어져 있기 때문’ 이다. 작은 문제가 큰 문제의 부분집하게 속해있는것! 기본적으로 다익스트라는 하나의 최단거리를 구할때 그 이전까지 구헀던 최단거리 정보를 그대로 사용한다는 특징이 있다.
-
다익스트라에서 요구되는 연산은 크게 두가지다.
- 모든 간선을 탐색하는 과정
- 우선순위 큐를 조작하는 연산
예제 문제!
- 이코테 - 화성탐사 https://velog.io/@xxwb__/이것이-코딩-테스트다-최단-거리-화성-탐사
- 백준 - 백준 18352 / 특정 거리의 도시 찾기 https://www.acmicpc.net/problem/18352
코드
- 힙을 활용한 다익스트라 알고리즘
def dijkstra(start):
q = []
# 시작노드로 가기 위한 최단 경로는 0으로 설정하며 힙에 삽입
heapq.heappush(q, (0, start))
distance[start] = 0
while q: # 힙이 비어 있지 않다면
# 가장 최단 거리가 짧은 노드 정보 꺼내기
dist, u = heapq.heappop(q)
# 현재 노드가 이미 처리된 적 있는 노드라면 무시
if distance[u] < dist:
continue
# 현재 노드와 연결된 다른 인접 노드들 확인
for i in graph[u]:
cost = dist + i[1]
if cost < distance[i[0]]: # relaxation
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 / 특정 거리의 도시 찾기
#https://www.acmicpc.net/problem/18352
#특정 거리의 도시 찾기
#18352
from collections import deque
import sys
input = sys.stdin.readline
# n = 도시개수 / m = 도로개수 / k = 거리 정보 / x = 출발도시 번호
n, m, k, x = map(int, input().split())
graph = [[] for _ in range(n+1)]
for i in range(m):
a, b = map(int, input().split())
graph[a].append(b)
graph[a].sort()
graph[b].sort()
# print(graph)
# visit = [0] * n*n
visit = [-1] * (n+1)
def bfs(graph, start, visit, k):
result = []
que = deque()
que.append(start)
visit[start] = 0
while que:
start = que.popleft()
for i in graph[start]:
if visit[i] == -1:
que.append(i)
visit[i] = visit[start] + 1
# if visit[i] == k:
# result.append(i)
return visit
visit = bfs(graph, x, visit, k)
ans = []
for i in range(len(visit)):
if visit[i] == k:
ans.append(i)
if ans:
for i in ans:
print(i)
else:
print(-1)참고자료
해보자! 게임 클라 개발자!