[알고리즘] 다익스트라 (Dijkstra)

최단 경로

 

[알고리즘 소개]

가중치가 존재하는 그래프에서 출발지가 정해졌을 때 해당 출발지에서 다른 정점으로 이동하는 최단 경로를 구하는 알고리즘.

 

 

[알고리즘 특징]

• 우선순위 큐 사용
• dp와 그리디
• 음수 간선 불가

[코딩 방법]

1. 인접 리스트 그래프를 정점과 가중치를 저장할 클래스(구조체)로 구성
2. dp용 배열과 클래스 타입 최소 우선순위 큐 생성
3. 시작점에 대해 배열의 가중치 0으로 초기화, 우선순위 큐에 시작점 정보 넣음
4. 우선순위 큐가 빌 때까지 원소를 제거
5. 제거한 원소에 대해 dp값보다 원소의 가중치가 더 큰 경우 가지치기
6. 가지치기 후 인접 정점 확인, dp값보다 작다면 dp 갱신 후 우선순위 큐에 삽입

[시간 복잡도]

$O(E logE)$ 

 

 

[공부용 링크]

m.blog.naver.com/ndb796/221234424646