다익스트라(Dijkstra)
음의 가중치가 없는 그래프에서 여러 개의 노드가 있을 때, 특정한 한 정점에서 출발해 다른 모든 정점으로 가는 최단 거리를 구하는 알고리즘이다.
다익스트라 특징
- 방문하지 않은 노드 중에서 가장 비용이 적은 노드를 선택한다.
→ 그리디 - 해당 노드로부터 갈 수 있는 노드들의 비용을 갱신한다.
→ 다이나믹 프로그래밍
주의할점
- 가중치는 항상 양수여야 한다.
- 출발 노드와 도착 노드 간의 최단 거리를 구하는 알고리즘이지만, 실제 완성된 최단 거리 배열에는 출발 노드와 모든 노드 간의 최단 거리가 기록되어 있다.
다익스트라 탐색과정
- 출발 노드를 설정한다.
- 최단 거리 배열을 초기화한다.
(출발 노드는 0, 이외의 노드는 무한(적당히 큰 값)으로 초기화) - 방문하지 않은 노드 중에서 가중치가 가장 작은 노드를 선택한다.
- 해당 노드를 거쳐 다른 노드로 가는 비용을 계산해 최단 거리 배열을 업데이트한다.
- 과정 3번~4번을 반복하며 최단 거리 배열을 완성한다.
최단 거리 업데이트 방법
Min(해당 노드의 최단 거리 배열값 + 가중치, 연결 노드의 최단거리 배열값)
다익스트라 구현방법
- 이차원 배열 사용(시간복잡도 - O(V^2))
- 우선순위 큐 사용(시간복잡도 - O(ElogV))
간선 수 : E / 노드 수 : V
@minzdev