최단경로(Shortest Path) 탐색 알고리즘으로 하나의 정점에서 출발했을 때 다른 모든 정점으로의 최단 경로를 구하는 알고리즘이다. 다만, 음의 간선을 포함할 수 없다. 플로이드 워셜 알고리즘과의 차이점은 다익스트라는 하나의 정점에서만 최단거리를 구하지만 플로이드 워셜은 그래프에서 가능한 모든 노드 쌍에 대해 최단 거리를 구하는 알고리즘이다.
다익스트라 알고리즘이 다이나믹 프로그래밍 문제인 이유는 최단거리는 여러개의 최단거리로 이루어져 있기 때문이다. 즉, 기본적으로 다익스트라는 하나의 최단거리를 구할 때 그 이전까지 구했던 최단 거리 정보를 그대로 사용한다는 특징이 존재한다.
📌 기본 작동과정
1. 출발 노드를 설정한다
2. 출발 노드를 기준으로 각 노드의 최소 비용을 저장한다.
3. 방문하지 않은 노드 중에서 가장 비용이 적은 노드를 선택한다.
4. 해당 노드를 거쳐서 특정한 노드로 가는 경우를 고려하여 최소 비용을 갱신한다
5. 위의 과정을 반복한다.
우선순위 큐를 이용한 다익스트라 : O(ElogE)
알고리즘
1. 초기화 - 우선순위 큐(pq), 거리(dist) 생성
2. 시작노드 갱신 - pq에 시작노드 넣고 거리 0으로 갱신
3. pq에서 노드 꺼내기
4. 만약 지금 꺼낸 노드보다 더 짧은 경로를 알고 있다면 무시
5. 아니라면 꺼낸 노드의 인접한 정점들을 검사
5-1. 더 짧은 경로를 발견하면, dist를 갱신하고 pq에 넣기
from queue import PriorityQueue
def dijkstra(start):
pq = PriorityQueue()
dist[start] = 0
pq.put((0, start)) # 거리,정점
while not pq.empty():
cost, node = pq.get()
if dist[node] < cost:
continue
for nw, nv in graph[node]:
if dist[nv] > (cost + nw):
dist[nv] = cost + nw
pq.put((cost + nw, nv))📝 백준 문제 추천
느리지만 확실하게 🐢