다익스트라 시간복잡도 (1) 썸네일형 리스트형 다익스트라(Dijkstra) 알고리즘 다익스트라 (Dijkstra) 다익스트라는 어떤 그래프에서 특정노드에서 특정노드까지의 최단거리를 구할때 쓰는 알고리즘이다. 바로 예시를 들어보자. 다음과 같은 그래프가 있다. 1번 노드에서 2번 노드로 가기위한 최소거리를 구할때 우리는 모든 엣지의 크기를 동시에 살피며 눈대중으로 찾을 것이다. 코딩을해서 찾는거보다 그냥 머리로찾는게 빠를거다. 그러나 노드의 개수가 많아지고 엣지의 개수가 많아지면 문제가 생긴다. 때문에 우리는 최단거리를 찾는 알고리즘을 통해 노드간의 최단거리를 찾아야 하는데 이에 대표적으로 사용되는 알고리즘이 바로 다익스트라이다. 설명 다익스트라는 BFS의 기본 틀에 우선순위 큐를 접목하여 구현할 수 있다. BFS에 대한 설명은 여기(링크)에 있당! 1번 노드에서 각 노드로 가기위한 최소.. 이전 1 다음
