Category: CE

0

Dijkstra Algorithm

다익스트라 알고리즘Dijkstra algorithm(이하 다익스트라 알고리즘)은 음의 가중치가 없는 그래프에서 한 노드에서 다른 모든 노드까지의 가장 짧은 거리를 구하는 알고리즘 중 하나이다. 선형구조로 구현된 다익스트라 알고리즘은 O(N^2)의 시간복잡도를 가지지만 힙을 이용해 구현하게 되면 O(NlogN)의 시간복잡도를 가지게 된다. 최단 거리를 구하는