[D-13] 다익스트라

📍 다익스트라

✅ 정의

다익스트라(dijjkstra) 알고리즘은 그래프에서 최단 거리를 구하는 알고리즘이다.
출발 노드와 이외의 모든 노드 간의 최단 거리를 표현하다. (출발-도착 노드 간의 최단거리가 아니다.)

이미지 출처 : 다익스트라, https://velog.io/@leejh96/%EB%8B%A4%EC%9D%B5%EC%8A%A4%ED%8A%B8%EB%9D%BCdijkstra

✅ 특징

- 출발 노드와 모든 노드 간의 최단 거리를 탐색한다.
- 에지는 모두 양수이다.
- 시간 복잡도는 O(ElogV)이다.(노드 수 : V, 에지 수 : E)

 

✅ 핵심 이론

1. 인접 리스트로 그래프 구현하기
2. 최단 거리 배열 초기화하기
3. 값이 가장 작은 노드 구하기
4. 최단 거리 배열 업데이트하기
5. 과정 3~4를 반복해 최단 거리 배열 완성하기

1. 인접 리스트로 그래프 구현하기
- 시간 복잡도 측면, N의 크기가 클 것을 대비해 인접 리스트를 선택하여 구현한다.
- 그래프의 연결을 표현하기 위해 인접 리스트에 연결한 배열의 자료형은 (노드, 가중치)와 같은 형태로 선언하여 연결한다.

---

2. 최단 거리 배열 초기화하기
- 출발 노드는 0, 이외의 노드는 무한으로 초기화한다.
- 이 때 무한은 적당히 큰 값을 사용하면 된다.

---

3. 값이 가장 작은 노드 구하기
- 최단 거리 배열에서 현재 값이 가장 작은 노드를 고른다.
- 다음에서는 값이 0인 출발 노드에서 시작하면 된다.

---

4. 최단 거리 배열 업데이트하기
- 선택된 노드에 연결된 에지의 값을 바탕으로 다른 노드의 값을 업데이트한다.
- 1단계에서 저장해 높은 연결 리스트를 이용해 현재 선택된 노드의 에지들을 탐색하고 업데이트하면 된다.
- 연결 노드의 최단 거리는 두 값 중 더 작은 값으로 업데이트한다.

---

5. 과정 3~4를 반복해 최단 거리 배열 완성하기
- 과정 4에서 선택 노드가 될 때마다 다시 선택되지 않도록 방문 배열을 만들어 처리한다.
- 모든 노드가 선택될 때까지 반복하면 최단 거리 배열이 완성된다.