[ALGORITHM] 다익스트라 알고리즘

최단 경로 문제

• 두 노드를 잇는 가장 짧은 경로를 찾는 문제
• 가중치 그래프(Weighted Graph)에서 간선(Edge)의 가중치 합이 최소가 되도록 하는 경로를 찾는 것이 목적

---

최단 경로 문제 종류

• 단일 출발 최단 경로 문제 : 그래프 내의 특정 노드 u에서 출발하여, 그래프 내의 모든 다른 노드에 도착하는 가장 짧은 경로를 찾는 문제
• 단일 도착 최단 경로 문제 : 모든 노드들로 부터 출발해서, 그래프 내의 특정 노드 u로 도착하는 가장 짧은 경로를 찾는 문제
• 단일 쌍 최단 경로 문제 : 주어진 노드 u와 v간의 최단경로를 찾는 문제
• 전체 쌍 최단 경로 :  그래프 내의 모든 노드 쌍 사이에 대한 최단 경로를 찾는 문제

---

다익스트라 알고리즘 (최단경로 알고리즘)

https://www.baeldung.com/java-dijkstra

• 다익스트라 알고리즘은 단일 출발 최단 경로 문제에 해당
• 하나의 정점에서 다른 모든 정점에 도착하는 가장 짧은 거리를 구하는 문제

---

다익스트라 알고리즘 로직

• 첫 정점을 기준으로 연결되어 있는 정점들을 추가해 가며, 최단 거리를 갱신하는 기법
• 너비우선탐색(BFS)와 유사하며, 첫 정점 부터 각 노드간의 거리를 저장하는 배열을 만든 후, 첫 정점의 인접 노드 간의 거리부터 먼저 계산하면서, 첫 정점부터 해당 노드간의 가장 짧은 거리를 해당 배열에 업데이트
• 우선순위 큐 MinHeap방식을 활용해서, 현재 가장 짧은 거리를 가진 노드 정보를 먼저 꺼냄

---

우선순위 큐를 활용한 다익스트라 알고리즘 

1. 첫 정점 기준으로 배열을 선언하여 첫 정점에서 각 정점까지의 거리를 저장
2. 우선 순위 큐에서 노드를 꺼냄
3. 2번 과정을 우선순위 큐에서 꺼낼 노드가 없을때 까지 반복

---

우선순위 큐를 활용한 다익스트라 알고리즘 시간복잡도

• 다익스트라 알고리즘은 각노드마다 인접한 간선들을 모두 검사하는 과정과 우선순위 큐에 노드 / 거리 정보를 넣고 삭제하는 과정으로 진행
• 인접한 간선들을 모두 검사하는 과정은 O(E) 시간이 걸림 (E는 간선의 약자)
• 우선순위 큐에 노드와 거리 정보 들어가는 과정은 그래프의 모든 간선이 검사 될때마다, 배열 최단 거리가 갱신 되고 우선순위 큐에 추가됨, 이때 추가는 간선마다 최대 한번 일어날 수있으므로 최대 O(E)의 시간이 걸리고 O(E)개의 노드 / 거리 정보에 대해 우선순위 큐 유지하는 작업은 O(logE)가 걸림
• 결론은 총시간 복잡도는 O(ElogE)