> For the complete documentation index, see [llms.txt](https://kde6260.gitbook.io/dev/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://kde6260.gitbook.io/dev/dijkstra.md).

# 다익스트라(Dijkstra)

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

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

![](/files/-LyZCe5CMNGrI1eV5E6P)

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

![](/files/-LyZM_RHzmd1-wAnIL5z)

위 그래프에서 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은 우선순위 큐로 구현한다.

![다익스트라 알고리즘에서 각 정점의 최단 거리가 결정되는 과정](/files/-LyZahFQ_GaNC70aVJiT)

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

```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)


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://kde6260.gitbook.io/dev/dijkstra.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.