Algorithm/Study
2021. 9. 24.
최단 경로 알고리즘 : 다익스트라
최단 경로 알고리즘은 그리디 알고리즘 및 다이나믹 프로그래밍 알고리즘의 한 유형으로 볼 수 있다. 다익스트라 최단 경로 알고리즘 개념 - 그래프에 여러 개의 노드가 있을 때, 특정한 노드에서 출발하여 다른 노드로 가는 각각의 최단 경로를 구하는 알고리즘이다. - '음의 간선'이 없을 때 사용할 수 있다. - GPS 소프트웨어 기본 알고리즘으로 채택되곤 한다. - 그리디 알고리즘으로 분류된다. (매번 가장 비용이 적은 노드를 선택해서 임의의 과정을 반복하기 때문) - heapq(우선순위 큐) 사용 시, 시간 복잡도 : O(ElogV) (V : 노드 개수, E : 간선 개수) 최단 거리가 가장 짧은 노드를 순차 탐색이 아니라 힙 자료구조를 사용함으로써 시간복잡도를 줄인다. 힙 자료구조를 이용하면 특정 노드까..
