TIL - 프로그래밍/Python 알고리즘
알고리즘 - 다익스트라
chaemj97
2022. 5. 4. 23:18
728x90
- 한 노드에서 다른 모든 노드까지 가는데 최소비용
- 작동 원리
- 간선 : 인접 리스트
- 거리 배열 : 초기값 무한대로 설정
- 힙 시작점 추가
- 힙에서 현재 노드 빼면서, 간선 통할 때 더 거리 짧아진다면
- 거리 갱신 및 힙에 추가
# 초기값 갱신
dist[K] = 0
# K는 시작 값
heapq.heappush(heap,(0,K))
while heap:
# w : 현재 비용, v : 현재 노드
w, v = heapq.heappop(heap)
# v가 갱신되기 전 경로면 그냥 버리기
if w != dist[v]:
continue
for nw,nv in edge[v]:
if dist[nv] > dist[v] + nw:
dist[nv] = dist[v] + nw
heapq.heappush(heap, (dist[nv],nv))
728x90
반응형