다익스트라
- 다익스트라 알고리즘은 그래프에서 최단 거리를 구하는 알고리즘이다.
| 기능 |
특징 |
시간 복잡도(노드 수: V, 에지 수: E) |
| 출발 노드와 모든 노드간의 최단 거리 탐색 |
에지는 모두 양수 |
O(ElogV) |
✅ 다익스트라 알고리즘의 핵심 이론
➡️ 1단계: 인접리스트로 그래프 구현하기
- 다익스트라 알고리즘은 인접 행렬로 구현해도 좋지만 시간 복잡도 측면, N의 크기가 클 것을 대비해 인접 리스트를 선택하여 구현하는 것이 좋다.
- 그래프의 연결을 표현하기 위해 인접 리스트에 연결한 배열의 자료형은 (노드, 가중치)와 같은 형태로 선언하여 연결한 점도 눈여겨 보는 것이 좋다.
➡️ 2단계: 최단 거리 배열 초기화하기
- 최단 거리 배열을 만들고, 출발 노드는 0, 이외의 노드는 무한으로 초기화 한다.
- 이때 무한은 적당히 큰 값을 사용하면 된다.
➡️ 3단계: 값이 가장 작은 노드 고르기
- 최단 거리 배열에서 현재 값이 가장 작은 노드를 고른다.
- 여기서는 값이 0인 출발 노드에서 시작된다.