# 다익스트라(Dijkstra)

* 최초작성일 \[2020.01.14]
* 1차 수정일 \[2020.01.16] - 다익스트라 알고리즘의 시간복잡도 정리
* 2차 수정일 \[2020.01.19] - 우선순위 큐로 구현했을 때 시간복잡도 수정 + 다른 구현방법 첨부 

아래와 같이 간선에 가중치가 부여된 두 그래프에서 정점 A와 B의 최단 경로를 선택하는 방법은 무엇일까?

![](https://1792721125-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-Lo8iAG2zHsS2e9mIAqX%2F-LyZ3HZcIbx84m0MUNyo%2F-LyZCe5CMNGrI1eV5E6P%2Fdi.jpg?alt=media\&token=e19ee5e2-af34-4884-8a8d-278300928c98)

BFS(Breadth First Search) 알고리즘은 그래프 내 모든 간선의 가중치가 동일하다는 가정 하에 두 정점 사이의 최단경로를 구하는 알고리즘이므로 위 그래프에서 최단 경로를 찾기에는 적절하지 않다. 이 때 사용할 수 있는 알고리즘이 **다익스트라(Dijkstra) 알고리즘**이다.

다익스트라 알고리즘은 

* 간선에 가중치가 존재하는 그래프에서
* 1개의 정점에서 각 모든 정점과의 최단 거리를 구할 때

사용하는 알고리즘이다.

### Edge Relaxation

`w(u, v)`가 정점 `u`와 `v` 사이의 가중치를 나타낸다고 하자. 출발정점이 `A`라고 할 때,

`w(A, B)` = `min(w(A, C) + w(C, B), w(A, C))`

라고 할 수 있다. 

BFS 알고리즘에서 `dist[v]`는 출발 정점에서 `v` 까지의 최단 경로를 저장하는 자료구조로, 값이 한 번 결정되고 나면 바뀌지 않았다. 하지만 다익스트라 알고리즘에서 `dist[v]`의 값은 정점을 탐색하면서 변경될 수 있으며, `dist[v]`에 저장되는 값은 출발 정점과 `v`사이의 최단 거리와 같거나 클 수 있다. 이렇게 정점을 탐색하면서 두 정점 사이의 최단거리를 찾아내는 과정을 edge relaxation(변 경감)이라고 한다.

```python
def relax(u, v):
  if dist[v] > dist[u] + w(u, v):
    dist[v] = dist[u] + w(u, v)
    prev[v] = u
```

정점 `v1`와 `v2` 사이에 있는 정점 `u`를 경유할지 말지 여부는 `relax(u, v)`를 통해 알 수 있다. (여기서 `dist[u]`는 출발 정점과 `u`의 최단거리인 것으로 이미 확정된 상태다.)

`dist[v2]` 가 `dist[u] + w(u, v2)` 보다 클 경우에는 `u`를 경유해야 하며 그렇지 않으면 경유하지 않는다.

`prev[v]`는 `v` 이전에 방문했던 정점을 나타낸다. 

### Dijkstra Algorithm

![](https://1792721125-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-Lo8iAG2zHsS2e9mIAqX%2F-LyZHXi2HI5oxRbi2Rlz%2F-LyZM_RHzmd1-wAnIL5z%2Frelaxation.jpg?alt=media\&token=3d96b8f5-ec57-4238-a2d5-9997a46e0dce)

위 그래프에서 edge relaxation을 통해 출발 정점 S와의 최단 거리가 확정된 정점은 `S`, `A`, `D`에 해당한다. `dist[B]`는 `w(D, B)`를 알기 전 까지는 확정할 수 없으며, `dist[C]`도 `w(D, C)`를 알기 전 까지 확정할 수 없다. 

`S`, `A`, `D`와 같이 이미 출발 정점과의 최단 거리가 확정된 정점들을 known region이라고 하며 하나의 집합으로 묶을 수 있다. 정점들을 순회하면서 relaxation을 통해 출발 정점과의 최단 거리가 확정될 때 이 집합에 추가되며, 집합에 가장 처음으로 추가되는 정점은 `S` 자기자신이다.  

이미 최단 거리가 확정된 정점들을 가지고 다른 정점들의 최단 거리를 계산할 때, relaxation이 최대한 적은 빈도로 발생하는 게 효율적일 것이다. relaxation이 최대한 적게 발생하도록 하려면 known region에서 dist가 제일 작은 정점과 인접한 것들을 우선으로 탐색해야 한다. 따라서 known region은 우선순위 큐로 구현한다.

![다익스트라 알고리즘에서 각 정점의 최단 거리가 결정되는 과정](https://1792721125-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-Lo8iAG2zHsS2e9mIAqX%2F-LyZUzuexTFbsXL8EbyB%2F-LyZahFQ_GaNC70aVJiT%2Fdijkstra.jpg?alt=media\&token=e439f1c4-0be0-4a8b-a3da-0296b4727ba8)

위 과정을 코드로 구현하면 아래와 같다.

```python
from math import inf


def dijkstra(G, start):
  dist = [inf for _ in range(len(G))]
  dist[start] = 0
  known_region = list()
  q = list()
  
  # 큐에 모든 정점의 번호를 삽입.
  for v in G:
    q.append(v)
  
  while q:
    # dist가 가장 작은 정점을 큐에서 꺼냄.
    min_dist = min([x for x in dist if x not in known_region])
    min_v = dist.index(min_dist)
    q.remove(min_v)
    
    # 인접한 정점의 dist를 갱신한다.
    for adj_v in adjacent_list(min_v):
      relax(dist, min_v, adj_v)
    
    known_region.append(min_v)


def relax(dist, u, v):
  if dist[v] > dist[u] + weight(u, v):
    dist[v] = dist[u] + weight(u, v)
    prev[v] = u        
```

###

### 시간복잡도

다익스트라 알고리즘의 시간복잡도는 기본적으로 

`|V| * {T(min(queue)) + T(relax(u, v))}`

이다. 

* 큐 안에서 dist가 가장 작은 정점을 찾는 데에는 큐에 있는 정점의 갯수만큼 시간이 소요된다. => `O(min(q))` = `O(|V|)`
* 각 정점과 인접한 정점들을 edge relaxation한다. => `O(relax(u,v))` = `O(|E|/|V|)`

`min(q)`와 `relax(u, v)`는 정점의 갯수만큼 실행되므로 시간복잡도는 `|V| * O(|V| + |E|/|V|)` = `O(|V|^2 + |E|) = O(|V|^2)` 이다. densed graph일 경우 대부 `|E|`가 `|V|`의 제곱이므로 시간복잡도는 여전히 `O(|V|^2)`이다. 

```python
  while q:
    # 큐에서 최소값을 찾는 데 최대 |V|만큼 소요.
    min_dist = min([x for x in dist if x not in known_region])
    min_v = dist.index(min_dist)
    q.remove(min_v)
    
    # 정점 1개 당 평균적으로 |E|/|V| 만큼 relax() 수행.
    for adj_v in adjacent_list(min_v):
      relax(dist, min_v, adj_v)
    
    known_region.append(min_v)
```

만약 큐가 힙 트리를 이용한 우선순위 큐로 구현되어 있다면 시간복잡도는 어떻게 될까?

```python
  from queue import PriorityQueue
  
  q = ProirityQueue()
  ...
  
  while q:
    # 큐에서 최소값을 찾는 데 최대 log 2 |V|만큼 소요.
    min_v = q.pop()    
    
    # 정점 1개 당 평균적으로 |E|/|V| 만큼 relax() 수행.
    for adj_v in adjacent_list(min_v):
      relax(dist, min_v, adj_v)
      q.change_priority()
```

최소 힙 트리에서 최소값(루트)를 삭제하고, 다음 최소값을 루트에 승격시키는 데 `log2|V|`만큼 소요된다. 따라서 시간복잡도는 `O(log|V|)`이다. relax가 한번 이뤄지고 나서는 정점의 dist가 변경되기 때문에 우선순위를 바꿔야 한다. 이 때의 시간복잡도 또한 `O(log|V|)`이다. 따라서 우선순위 큐를 사용했을 때 시간복잡도는 `|V| * O(log|V| + |E|/|V| * log|V| )` = `O(|V| * log|V| + |E| * log|V|)` 이다.

큐의 2가지 형태를 비교해봤을 때 그래프 내 정점의 갯수가 많을수록 우선순위 큐를 사용하는 게 더 효율적임을 알 수 있다.

> 큐에 pop/push 연산 없이 change\_priority()를 수행하는 빌트인 함수가 파이썬에는 없다. 따라서 처음부터 큐에 모든 정점을 삽입하지 않고 다익스트라를 구현하는 방법을 쓰는 게 낫다. ([여기](https://kde6260.gitbook.io/dev/algorithm-quiz/dijkstra) 참고)

출처

* [코세라 알고리즘 강](https://www.coursera.org/learn/algorithms-on-graphs?specialization=data-structures-algorithms)