[알고리즘] 다익스트라

다익스트라

: 그래프에서 하나의 고정된 노드로부터 다른 노드로의 최단경로를 구하는 알고리즘
: ex) 1번 노드에서 다른노드로 가는 최단 경로는?

원리

• 시작 노드부터 각 노드까지의 거리를 저장하는 배열을 이용하여 탐색을 진행하면서 현재 누적 최단 거리와 간선의 가중치의 합이 이동하는 노드까지의 저장된 최단거리보다 작을 경우 업데이트
• priority queue를 이용하여 업데이트 된 값을 저장해주어 항상 최단 거리가 짧은 순서부터 탐색하도록 하여 시간 복잡도를 줄임
• 노드 방문 여부를 확인하는 배열을 이용하여 방문이 완료된 노드는 건너뒤며. 모든 노드를 방문하거나 더 이상 방문하지 않은 노드를 선택할 수 없을 때 종료