다익스트라 란?

다이나익 프로그래밍을 활용한 최단 경로 탐색 알고리즘

• 특정 한 노드에서 다른 노드까지의 최단 경로 탐색
• 이전 노드까지의 거리를 갱신한 다음, 노드로의 최단거리를 계산한다면, 이전의 노드까지의 최단거리를 갱신할 필요가 없기에 다이나믹 프로그래밍(DP)(메모제이션)를 이용한 것.
• 연결된 노드 중 가장 가까운 노드를 선택한다는 것이 특징

다익스트라 사용목적

• 특정한 하나의 정점에서 다른 모든 정점으로 가는 최단 경로를 알려줌.
• 그래프를 모두 확인하면서 메모제이션을 통해 최단 경로를 갱신
• 모든 가중치가 양수일 때만 사용가능 (현실에서는 음수가 나올 수 없기에 현실에서 사용 굿)

다익스트라 과정

1. 출발 노드 설정
2. 출발 노드를 기준으로 각 노드의 최소 비용 저장, 방문처리
3. 방문하지 않는 노드 중에서 가장 비용이 적은 노드 선택, 방문처리
4. 3번에서 선택한 노드를 거쳐 특정한 노드로 가는 경우를 고려해 최소 비용 갱신
5. 3~4번 반복

시간 복잡도

▶ O(V^2) -힙 트리를 사용하지 않을 때 = 연결된 모든 노드를 방문해야 함.
▶ O((V+E)logV) - 힙 트리를 사용했을 때 = 연결된 노드 중 최단거리를 가지는 노드만 방문
ㄴ 힙 트리를 이용하면 더 나은 시간 복잡도
: 각 노드마다 미방문 노드 중 출발점으로부터 현재까지 계산된 최단 거리를 가지는 노드를 찾는데 O(VlogV)의 시간이 필요, 각 노드마다 이웃한 노드의 최단 거리를 갱신할 때 O(ElogV)O(ElogV)의 시간이 필요하기 때문

(V는 정점의 개수, E는 한 정점의 주변 노드)

관련 예제 프로그래머스 배달

더 알기-동빈나