[알고리즘] 다익스트라(Dijkstra) - 최단거리 알고리즘

다익스트라(Dijkstra) 다익스트라 알고리즘은 음의 가중치(음의 간선, 음의 값)가 없는 그래프에서 최단 거리를 구하는 알고리즘입니다. 가장 짧은 경로를 찾으므로 "길 찾기" 문제에 많이 사용됩니다. 이전 다익스트라의 경우 O(n^2)의 시간복잡도를 가졌었지만, 현재는 우선순위 큐를 이용한 개선된 다익스트라 알고리즘이 탄생해 O(ElogE)의 시간복잡도를 가집니다. ( E는 Node의 간선의 수 ) 만약 음의 간선이 존재한다면 "벨만-포드 알고리즘"을 활용해야 합니다. 다익스트라 알고리즘은 그리디 알고리즘과 다이나믹 프로그래밍 기법을 사용한 알고리즘입니다. 그 이유는 아래의 알고리즘 특징에서 설명하겠습니다. 다익스트라 알고리즘 특징 각 지점은 그래프에서 '노드' 또는 정점으로 표현되고 지점간 연결된 ..