다익스트라

다익스트라 알고리즘이란?

음의 가중치가 없는 그래프의 한 정점에서 모든 정점까지의 최단거리를 각각 구하는 알고리즘이다.

쉽게 말해, 한 정점에서 다른 정점으로 이동할 때 가장 빠른 길을 찾아주는 알고리즘이다.

설명

1. 시작 정점에서 다른 정점으로 가는 모든 거리를 최댓값으로 설정한다.
2. 그리곤 시작 정점과 연결된 정점의 거리로 업데이트 해준다.

3. 시작 정점과 연결된 정점과 연결된 정점들을 순회하면서 더 짧은 거리로 업데이트 해준다.
4. 1번과 연결된 2번 정점과 연결된 정점을 순회하면서 2를 거쳐가는 것과 1번에서 직접 가는 것을 비교하여 더 짧은 거리로 경로와 거리를 업데이트 해준다.

5. 이런식으로 모든 경로를 탐색하여 시작 정점에서 다른 정점으로 가는 가장 짧은 거리를 모두 업데이트 해준다.

시간복잡도

O(V^2)

V: 노드의 숫자, E: 간선의 숫자라고 할 때, 기본 알고리즘의 시간복잡도는 O(V^2) 이다.

우선순위 큐를 사용해서 이를 좀 더 개선 할 수 있다.

방법은 2가지인데, 1번째로는 각 정점마다 인접한 간선들을 모두 검사하는 작업이고, 2번째로는 우선순위 큐에 원소를 넣고 삭제하는 작업이다.

모든 간선이 한번씩 검사된다는 점에서 첫 번째 작업이 O(E), 각 간선마다 우선수위 큐에 자료가 삽입 연산이 일어난다는 점에서 O(ElogE)이며, 이 둘을 합쳤을 때, (E+ElogE)의 시간복잡도는 O(ElogE)가 된다.

대개의 그래프의 경우 V^2 > E이므로 O(logE) = (logV)이고, 따라서, 시간 복잡도는 O(ElogV)가 될 수 있다.