Dijkstra 알고리즘

Dijkstra 알고리즘이란 ?

• 시작 정점에서 거리가 최소인 정점을 선택해 나가면서 최단 경로를 구하는 방식
• 음의 간선이 존재하지 않는, 간선의 값이 0 이상의 양수일 때 정상적으로 동작한다. 
• 우선 순위 큐(heapq)를 사용한다.

 

동작 원리 단계

1. 인접 리스트를 만든다.
2. 최단 거리 테이블을 무한대의 값으로 초기화한다.
3. 현재 노드에서 갈 수 있는 노드 다 가져온다.
4. 현재 노드에서 다음 노드로 가는 간선 비용을 계산하여 가중치 테이블을 업데이트 한다.
5. 3번과 4번을 반복한다. 

 

문제

SWEA - 5251. 최소이동거리