반응형 최단거리1 [Coding Test][Python][Shortest Path] Dijkstra Algorithm(다익스트라) 개념 및 예제 1. Dijkstra Algorithm 이란?Dijkstra 알고리즘이란 Weighted Graph에서 시작점과 도착점이 주어졌을 때 최단 경로(Shortest Path)를 찾는 알고리즘이다.시작 Node에서 출발하여 각 Node 까지의 최단 거리를 점진적으로 갱신하며 계산한다. 탐색은 "이미 방문한 Node"와 "방문하지 않은 Node"를 구분하여 진행되며, 방문한 Node로 가는 경로 중에서 가장 짧은 경로를 선택해 나간다. 알고리즘 동작 과정1) Adjance List & Priority Queue 사용Priority Queue에 시작 Node 추가우선 순위가 가장 높은(Distrance가 가작 작은) Node 추출방문 여부 확인Distance Update현재 Node에 연결된 Node를 Prio.. 2025. 1. 30. 이전 1 다음 반응형
