Sanjoy Dasgupta가 저술한 책인 Algorithms과 이기창님의 블로그를 참고하였다.

1. Dijkstra Algorithm

다익스타라 알고리즘은 최단경로문제 중, 하나의 정점에서 다른 모든 정점까지의 최단경로를 구하는 알고리즘이다. 너비우선탐색(BFS)을 적용하며 알고리즘은 다음과 같다.

1. 모든 노드를 무한대로 설정
2. 시작노드 선택. 시작노드로부터 시작노드까지 거리는 0이므로 노드의 숫자를 0으로 설정
3. 인접한 노드 중, 엣지의 가중치가 최소인 노드 선택
4. 시작노드(0)로부터 해당 노드까지의 거리(엣지의 가중치)를 해당 노드의 숫자로 업데이트
5. 만약 새로 연결된 노드로부터 임의의 노드까지의 거리가 시작노드로부터 해당 노드의 거리보다 짧다면 Edge Relaxation 진행
6. 더 이상 탐색할 노드가 없을 때 까지 반복

이 과정을 그림으로 차근차근 살펴보면 다음과 같다.

먼저 시작노드 $s$를 선정한다.
$s$와 인접한 노드 $t, y$에 거리정보를 업데이트 해준 뒤, 엣지의 가중치가 더 짧은 $y$로 경로를 만든다.
이번에는 $y$와 인접한 노드 $t, x, z$에 대해 거리정보를 업데이트함. 이때, $s$에서 $t$로 가면 10이 걸리는데, $s$에서 $y$로 갔다가 $t$로 가면 8이 걸림. 따라서 (c)처럼 $t$의 거리정보를 8로 업데이트 해준다.

다음으로, (d)와 같이 $y$에서 가장 인접한 노드인 $z$에 대해서도 이 과정을 반복해준다. 기존에 $y$에서 $x$로 엣지가 연결되었기 때문에 $s$로부터 $x$까지의 거리는 14였지만 $z$를 통해서 가면 13으로 줄게 된다.
이어서 $t$를 기준으로 이 과정을 반복하면, $x$까지의 거리가 9로 줄게 된다. 끝났다…

2. Dijkstra Algorithm 특징

엣지의 가중치가 음수인 경우 사용할 수 없다. 모든 엣지의 가중치가 음수라면 계속 최단경로를 갱신하는 오류를 범하기 때문이다. 따라서 엣지의 모든 가중치는 양수여야 한다.

3. Dijkstra Algorithm의 시간복잡도

• 우선순위 큐를 사용하는 경우

  먼저 모든 간선을 검사하기 때문에 $O(\left\vert E \right\vert)$의 시간이 소요된다.
  그리고 최악의 시나리오는 그래프의 모든 간선이 검사될 때마다 dist가 갱신되고 우선순위 큐에 노드의 번호가 추가되는 것이다. 이때 추가는 각 간선마다 최대 한 번 일어나기 때문에, 우선순위 큐에 추가되는 최대 원소의 수는 $O(\left\vert E \right\vert)$이고, 추가/삭제하는 시간은 $O(\log E)$이므로 전체 시간복잡도는 $O(\log E)$이다. 따라서 총 시간복잡도는 이들의 합인 $O(\log E)$이고, 대부분의 그래프는 $E \leq V^2$이므로 최종 시간복잡도는 $O(E\log V)$이다.

• 우선순위 큐를 사용하지 않는 경우

  먼저 시작노드로부터 거리가 가장 작은(인접한) 노드를 가려내야 한다. 이때, 최악의 경우에는 모든 노드를 따져봐야 하므로 $O(\left\vert V \right\vert)$ 시간이 소요된다. 이때, 한 노드당 엣지의 기댓값은 $E/V$이고, 이 연산을 전체 노드 수만큼 반복하므로 $O(V^2+E)$이 소요된다. 대부분의 그래프는 $E \leq V^2$이므로 최종 시간복잡도는 $O(V^2)$이다.

4. Dijkstra Algorithm 기타 설명

• 다익스트라 알고리즘을 이용할 때, 2번째로 짧은 경로를 찾는 방법

  $\rightarrow$ 그냥 2번째 최단경로까지 저장하면 된다.

• 다익스트라 알고리즘을 음수 가중치일 때 이용하는 방법

  $\rightarrow$ 가장 작은 가중치의 절댓값을 모든 엣지 가중치에 더해준 뒤, 다익스트라 알고리즘을 돌리고 다 끝나면 다시 해당 절댓값만큼 빼주면 된다.