다익스트라 (Dijkstra)
- 그래프에서 최단 거리를 구하는 알고리즘
- 출발 노드와 모든 노드 간의 최단 거리 탐색
- 에지는 모두 양수
=> 음의 가중치가 없는 그래프의 한 노드에서 모든 노드까지의 최단 거리를 구하는 알고리즘
- 시간 복잡도 : O(ElongV) (E : 에지 수, V : 노드 수)
- 우선순위 큐를 사용
- 기본적으로 Greedy와 DP 알고리즘을 사용한 기법
1. 방문하지 않은 노드 중 가장 비용이 적은 노드 선택 (그리디)
2. 해당 노드로부터 갈 수 있는 노드들의 비용 갱신 (DP)
- 위의 두 단계를 반복하여 각 모든 노드 까지의 최단 거리를 구함
🌝 핵심 이론
1. 인접 리스트로 그래프 구현하기
- 인접 행렬로 구현도 가능하지만 시간 복잡도를 고려한다면 인접 리스트를 사용하는 것이 좋음
2. 최단 거리 배열 초기화하기
- 최단 거리 배열을 만들고, 출발 노드는 0, 이외의 노드는 아주 큰 값으로 초기화
3. 값이 가장 작은 노드 고르기
- 최단 거리 배열에서 현재 값이 가장 작은 노드 고르기
4. 최단 거리 배열 업데이트 하기
- 선택된 노드에 연결된 에지의 값을 바탕으로 다른 노드의 값을 업데이트
- 1단계에서 저자해 둔 연결 리스트를 이용해 현재 선택된 노드의 에지들을 탐색하고 업데이트
- 연결 노드의 최단 거리는 다음과 같이 두 값 중 더 작은 값으로 업데이트
MIn(선택 노드의 최단 거리 배열의 값 + 에지 가중치, 연결 노드의 최단 거리 배열의 값)
5. 3-4를 반복해 최단 거리 배열 완성하기
🌝 유의할 점
- 출발 노드와 도착 노드 간의 최단 거리를 구하는 것이 아닌 출발 노드와 이외의 모든 노드 간의 최단 거리를 표현
