[Python] 최단 경로 - 다익스트라 알고리즘(Dijkstra's algorithm)

다익스트라 알고리즘

 

다익스트라 알고리즘은 그래프의 한 노드에서 다른 노드로 가는 최단 경로를 구하는 알고리즘이다. 그래프의 노드를 잇는 간선에는 거리 정보가 주어진다. 다익스트라 알고리즘은 이 거리가 양수여야 한다.

 

다익스트라 알고리즘 구현

1. 주어진 그래프 구현

2. 최단 거리 리스트를 생성

3. 최단 거리 리스트에서 가장 작은 값을 가지는 노드 선택

4. 최단 거리 리스트 업데이트

- 선택한 노드의 최단거리 + 도착 노드까지의 거리와 도착 노드의 최단거리를 비교해서 작은 값으로 도착 노드의 최단 거리를 업데이트 한다.

이 과정을 반복해서 최단거리 리스트를 업데이트한다.

 

효율적인 다익스트라 알고리즘을 구현하기 위해 우선순위 큐를 사용해서 구현한다.

파이썬의 heapq 모듈을 통해 우선순위 큐를 사용할 수 있다.

 

#우선순위 큐란?

큐의 원소들이 우선순위를 가지고 있는 것을 말한다. 
큐는 원래 먼저 들어온 원소가 먼저 나가는데 우선순위 큐에서는 우선순위가 높은 원소가 먼저 나간다. 

 

- 그래프의 정점, 거리를 우선순위 큐에 삽입
- 우선순위 큐에서 최소 값 추출

heapq는 튜플을 입력값으로 받는다. 주어진 튜플의 첫번째 값을 기준으로 우선순위가 설정되기 때문에 (거리, 노드)를 넣으면 거리를 기준으로 우선순위가 부여된다. 값이 작을수록 우선순위가 높다.

import heapq

heap=[]
heapq.heappush(heap, 3)
heapq.heappush(heap, 6)
heapq.heappush(heap, 8)
heapq.heappush(heap, 2)

print(heapq.heappop(heap))

출력값

2

 

기본적으로 heapq가 동작하는 방식이다.

다익스트라 알고리즘을 구현할 때는 아래와 같은 방식으로 사용한다.

 

import heapq

heap=[]
heapq.heappush(heap, (3, 4))
heapq.heappush(heap, (6, 2))
heapq.heappush(heap, (8, 3))
heapq.heappush(heap, (2, 1))


print(heapq.heappop(heap))

출력값

(2, 1)

앞에 있는 값을 기준으로 우선순위가 부여되기 때문에 heappop을 하면 (2,1)이 출력된다.

 

 

#다익스트라 알고리즘 문제

https://www.acmicpc.net/problem/1753

1753번: 최단경로