동적계획법 - 다익스트라 알고리즘

최단거리 알고리즘으로 알려진 다익스트라 알고리즘에 대해서 공부해보았습니다.

다익스트라 알고리즘을 푸는 방법에는 최소 우선 큐를 사용하느냐와 안사용하느냐 두 가지 방법이 있다.

최소 우선큐를 사용하지 않으면 시간복잡도가 O(V2)가 나오는 반면, 최소 우선 큐를 쓰면 O(E+VlogV) 시간복잡도가 나오기 때문에 최단 경로 알고리즘 중 점근적으로 가장 빠른 알고리즘이라고 한다.

알고리즘 간략 요약

1. 모든 꼭짓점을 미방문 상태로 표시 - 모든 미방문 꼭짓점의 집합을 만든다.

2. 모든 꼭짓점에 시험적 거리 값을 부여한다. 초기점은 0으로, 다른 모든 꼭짓점은 무한대로 설정한다. (초기점은 현재 위치)

3. 현재 꼭짓점에서 미방문 인접 꼭짓점을 찾아 시험적 거리를 현재 꼭짓점에서 계산

4. 새로 계산한 시험적 거리를 현재 부여된 값과 비교해서 더 작은 값을 넣는다.

5, 현재 노드에 인접한 모든 미방문 꼭짓점을 계산했다면, 현재 꼭짓점을 방문한 것으로 표시하고 미방문 집합에서 제거

6. 방문한 꼭짓점은 다시는 방문하지 않는다.

7. 도착점이 방문한 상태로 표시되거나 미방문 집합에 있는 꼭짓점들의 시험적 거리 중 최솟값이 무한대이면 멈춘다. 후자의 경우는 초기점과 나머지 미방문 집합 간에 연결이 없을 때 일어난다.

8. 7의 경우가 아니면 시험적 거리가 가장 작은 다음 미방문 꼭짓점을 새로운 '현재 위치'로 선택하고 3단계로 돌아간다.

유사코드

1  function Dijkstra(Graph, source):
 2
 3      create vertex set Q
 4
 5      for each vertex v in Graph:             // 초기화
 6          dist[v] ← INFINITY                           // 소스에서 v까지의 아직 모르는 길이
 7          prev[v] ← UNDEFINED                          // 소스에서 최적 경로의 이전 꼭짓점
 8          add v to Q                                // 모든 노드는 초기에 Q에 속해있다 (미방문 집합)
 9
10      dist[source] ← 0                                 // 소스에서 소스까지의 길이
11
12      while Q is not empty:
13          u ← vertex in Q with min dist[u]         // 최소 거리를 갖는 꼭짓점
14                                                            // 을 가장 먼저 선택한다
15          remove u from Q
16
17          for each neighbor v of u:           // v는 여전히 Q에 있다.
18              alt ← dist[u] + length(u, v)
19              if alt < dist[v]:               // v 까지의 더 짧은 경로를 찾았을 때
20                  dist[v] ← alt
21                  prev[v] ← u
22
23      return dist[], prev[]

//백준 알고리즘 문제를 풀 때, 나는 우선순위 큐를 사용하지 않고, 배열은 주어진 그래프 배열, 거리 저장 배열, 방문확인 배열 총 3개의 큰 배열을 사용하여 풀었다.