다익스트라(Dijkstra) 알고리즘

 

23. 다익스트라(Dijkstra) 알고리즘

 

 

1. 출발 노드를 설정합니다.
  2. 출발 노드를 기준으로 각 노드의 최소 비용을 저장합니다.
  3. 방문하지 않은 노드 중에서 가장 비용이 적은 노드를 선택합니다.
  4. 해당 노드를 거쳐서 특정한 노드로 가는 경우를 고려하여 최소 비용을 갱신합니다.
  5. 위 과정에서 3번 ~ 4번을 반복합니다.

 

 

 

최소 비용을 단순히 선형 탐색으로 찾도록 만들었습니다. 이렇게 작성하는 경우 다익스트라의 시간 복잡도가 O(N^2)으로 형성됩니다. 따라서 최대한 빠르게 작동시켜야 하는 경우 힙 구조를 활용하여 시간 복잡도 O(N * log N)을 만들 수 있습니다. 특히 위와 같은 소스코드는 정점의 갯수가 많은데 간선은 적을 때 치명적일 정도로 비효율적으로 작동할 수 있습니다.

인접 리스트 방식을 활용하여 시간 복잡도 O(N * log N)으로 구현한 것입니다. 이 경우 정점에 비해 간선의 갯수가 비정상적으로 적어도 안정적으로 처리할 수 있습니다.