📚 목차
요약
1. 다익스트라(Dijkstra)
1. 다익스트라 알고리즘
- 그래프에서 최단 거리를 구하는 알고리즘
- 단순히 시작 노드부터 도착 노드까지의 최단 거리를 구하는 것이 아닌 시작 노드 외의 모든 노드와의 최단 거리를 구하는 것이다.
| 기능 |
특징 |
시간복잡도(노드 수: V, 에지 수: E) |
| 출발 노드와 모든 노드 간의 최단 거리 탐색 |
에지는 모두 양수 |
O(ElogV) |
2. 다익스트라 알고리즘의 핵심 이론
- 인접 리스트로 그래프 구현하기
| 1 |
2, 8 |
3, 3 |
| 2 |
4, 4 |
5, 15 |
| 3 |
4, 13 |
|
| 4 |
5, 2 |
|
| 5 |
|
|
- 최단 거리 배열 초기화 하기
- 출발 노드는 0, 나머지 노드는 무한으로 초기화 한다.