다익스트라 알고리즘에 대해 설명하세요
Keyword
양의 가중치, 최단거리 테이블, 우선순위 큐
Script
BFS가 가중치가 없는 상황에서 그래프에서의 최단거리 탐색에 쓰인다면, 다익스트라 알고리즘은 각 간선이 서로 다른 양의 가중치로 이루어진 그래프에서 특정 지점에서 특정 지점까지의 최단거리 탐색에 쓰입니다.
먼저, 시작 정점의 거리를 0, 나머지를 무한대로 설정해두고 시작합니다. 이후 현재 정점에 연결된 간선들을 조회하며, 나머지 정점까지의 거리를 갱신해주는 작업을 반복적으로 수행하면 모든 간선을 고려한 최단거리 테이블이 완성됩니다.
추가적인 자료구조 없이는 O(V^2)의 시간복잡도를 갖지만, 우선 순위 큐를 사용하면 O(ElogV)의 시간복잡도로 수행이 가능한 알고리즘입니다.
Additional
시간복잡도
기본적으로 모든 노드를 방문하고 이에 연결된 노드를 탐색하기 때문에 시간복잡도는 O(노드 수 ^ 2)이다.
하지만 우선순위 큐를 사용하면, 각 정점에서 최소 거리를 가진 다음 노드를 탐색하는데 O(n)이 아닌 O(log n)으로 수행할 수 있기 때문에, O(ElogV)로 최단거리를 찾을 수 있다.
모든 간선이 한번씩 검사된다는 점에서 첫 번째 작업이 O(E), 각 간선마다 우선수위 큐에 자료가 삽입 연산이 일어난다는 점에서 O(ElogE)이며, 이 둘을 합쳤을 때, (E+ElogE)의 시간복잡도는 O(ElogE)가 된다.
대개의 그래프의 경우 V^2 > E이므로 O(logE) = (logV)이고, 따라서, 시간 복잡도는 O(ElogV)가 될 수 있다.
with programming