Algorithm
최단 경로 알고리즘 - 다익스트라 (Dijkstra)
snail voyager
2020. 4. 5. 19:17
728x90
반응형
다익스트라 (Dijkstra)
- 단일 시작점에서 다른 모든 정점까지 최단 경로
- 음수 가중치, 사이클이 있는 그래프 불가
- 인접리스트, 우선순위큐 사용
- 정점에서 가까운 순으로 다음 정점 선택 (탐욕적)
- O((E+V)logn)
- 최단 경로 갱신 가능
728x90
반응형