# 다익스트라

## **1. 기초**

**가중치가 있는 그래프**에서 **한 정점에서 다른 모든 정점까지의 최단 경로**를 찾는 알고리즘

[이해하기 쉬운 설명](https://www.youtube.com/watch?v=o9BnvwgPT-o\&t=642s)

1. 매 단계마다 도달할 수 있는 정점 중에서 **시작점으로부터의 거리가 가장 가까운 정점**을 구하고, 해당 **거리를 확정**한다.
2. 거리가 확정되면 해당 정점과 **연결된 정점들의 거리도 갱신**해준다.

'dp + 그리디'로 이해하면 된다. 다익스트라는 "**항상 최소만 찾는 미친놈**"이다.

간단하게 생각하여, 매 순간마다 최소 거리인 놈들을 확정하면 최소 거리가 아닌 정보가 있을 수 없다.

<figure><img src="/files/KHYxxr8fatBUq6T3GfIO" alt=""><figcaption></figcaption></figure>

1번째로 탐색하는 정점은 자기 자신이니까 거리가 0인게 자명. 2번째로 탐색하는 정점은 자기 자신으로부터 직접 이어진 정점이니까 최소 거리인게 자명.

3번째로 탐색하는 정점이 2번째 정점과 이어져있다면 기존에 저장돼있던 (1번 \~ 3번)의 가중치와 (2번 \~ 3번) 간선 중 최솟값을 저장하고 최소 거리 확정.

하필 (1번 \~ 3번) 과 (2번 \~ 3번)의 가중치가 너무 커서 (1번 \~ A번 \~ B번 \~ C번 \~ 3번)의 거리가 더 작을수도 있는거 아니냐고?

그러면 A번 정점을 고르지 3번 정점을 고를 수가 없음. (음수 간선이 있지 않는 한) 3번 정점을 골랐다는 말은, A번 정점은 그것보다 더 큰 가중치를 가졌다는 말임.

## **2. 시간 복잡도**

V : 정점(노드) 개수 E : 간선(엣지) 개수

**간단한 배열 사용 : O(V^2)**

방문하지 않은 정점 중 시작점에서 가장 가까운 정점을 찾기 위해 시작점에서 모든 정점까지의 최소 거리를 일일이 탐색하면 매번 최단 거리를 구하는 데 O(V)의 시간이 걸리고, 이를 모든 정점에 대해 반복하면 O(V^2)

**우선순위 큐 사용 : O((E+E) log V)**

인터넷 설명들은 O((E+V) log V)로 나와있는데 구현은 O((E+E) log V)로 다르게 돼있다고 함.

'다익스트라 알고리즘은 그리디 알고리즘이기 때문에 A->C(비용+4) 대신 A->B(비용+3)을 선택 후 B를 방문처리하게 된다. 현재는 나쁘지만 미래에는 좋은 결과를 불러오는 A->C(비용+4)\&C->B(비용-5) 경로(비용-1)를 선택하지 않게 되고 올바른 해를 도출할 수 없게 된다'라는 설명은 **이 구현에서는 들어맞지 않게 된다.**

## **3. 우선순위 큐를 이용한 다익스트라 (실제 구현)**

1. 우선순위 큐에 (0, 시작점) 추가
2. 우선순위 큐에서 거리가 가장 작은 원소를 선택, 해당 거리가 최단 거리 테이블에 있는 값과 다를 경우 넘어감
3. 원소가 가리키는 정점을 V라고 할 때, V와 이웃한 정점들에 대해 최단 거리 테이블 값보다 V를 거쳐가는 것이 더 작은 값을 가질 경우 최단 거리 테이블의 값을 갱신하고 우선순위 큐에 (거리, 이웃한 정점의 번호)를 추가
4. 우선순위 큐가 빌 때까지 2, 3번 과정을 반복

결국 모든 간선에 대해 한 번씩 연산하게 됨. 우선순위 큐에 넣는 연산 포함하면 logN 곱해야됨.

이전에 최소값만 찾는 미친놈 모드에서 살짝 순해진 대신 시간 복잡도 낮아진다. 최소가 갱신되면 우선순위 큐에 정점을 추가한다. 이외엔 똑같이 행동.


---

# Agent Instructions: 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://lazyartisan.gitbook.io/note/main-page/algorithm/undefined/undefined-2.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.