● 자료구조 우선순위 큐
- 자료 중 최소 or 최대 값을 먼저 출력한다. (기본적으로 최소)
- 라이브러리 heapq를 사용한다.
- 입력(heapq.heappush(list, value), 출력(heapq.heappop(list))
● 다익스트라 알고리즘 (시작 지점부터 최단거리를 구하는 알고리즘)
1. 경로가 가장 짧은 노드 부터 탐색
2. 최단 거리 list를 무한으로 설정한다.
3. 노드 중에서 가장 짧은 거리를 갖고 있는 노드를 방문한다.
4. 현재 노드와 연결된 노드들의 거리를 계산하고 최단거리 list를 갱신한다.
5. 3,4를 반복한다. 모든 노드를 방문할 때까지
● 코드로 구현
import heapq
graph = [[] for _ in range(n+1)] # 각 노드가 연결된 정보(다음노드,거리)
inf = int(1e9)
distance = [inf]*(n+1) # 최단거리 정보 처음엔 무한으로 설정
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 n,d in graph[now]:
cost = dist + d
if cost < distance[n]:
distance[n] = cost
heapq.heappush(q,(cost,n))
'python > 알고리즘' 카테고리의 다른 글
[알고리즘] DFS/ BFS (0) | 2021.02.13 |
---|
댓글