[알고리즘] 다익스트라(Dijkstra) 알고리즘

최단경로 알고리즘

• 특정한 노드에서 출발하여 다른 모든 노드로 가는 최단 경로를 계산
• 음의 간선이 없을 때 정상적으로 동작 - 현실 세계의 도로
• 그리디 알고리즘으로 분류
  - 매 상황에서 가장 비용이 적은 노드를 선택해 임의의 과정을 반복

동작 과정

1. 출발 노드를 설정
2. 최단 거리 테이블을 초기화
3. 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택
4. 해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블 갱신
5. 위 과정에서 3-4번을 반복

• 알고리즘 동작 과정에서 최단 거리 테이블은 각 노드에 대한 현재까지의 최단 거리 정보를 가지고 있음

• 단계를 거치며 한 번 처리된 노드의 최단 거리는 고정되어 더 이상 바뀌지 않음
  - 한 단계당 하나의 노드에 대한 최단 거리를 확실히 찾는 것

• 다익스트라 알고리즘 수행 뒤, 최단 거리 테이블에 각 노드까지의 최단 거리 정보가 저장

구현 방법

1. 선형탐색 이용

• 단계마다 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택하기 위해 매 단계마다 1차원 테이블의 모든 원소를 확인(순차 탐색)

• 성능 분석
  - 총 O(V)번에 걸쳐서 최단 거리가 가장 짧은 노드를 매번 선형 탐색
  - 전체 시간 복잡도 : O(V^2)
  

2. 우선순위 큐 이용

• Priority Queue - 최소 힙, 최대 힙
  우선 순위가 가장 높은 데이터를 가장 먼저 삭제하는 자료구조!

• 다익스트라 알고리즘 개선된 구현 방법
  - 단계마다 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택하기 위해 힙(Heap)자료구조 사용
  - 현재 가장 가까운 노드를 저장해 놓기 위해서 힙을 추가적으로 사용
  - 현재 최단 거리가 가장 짧은 노드를 선택해야 하므로 최소 힙 사용
  

• 성능 분석
  - 시간 복잡도 O(ElogV)
  - 현재 우선순위 큐에서 꺼낸 노드와 연결된 다른 노드들을 확인하는 총 횟수는 최대 간선의 개수 만큼 연산 수행
  - 직관적으로 전체 과정은 E개의 원소를 우선순위 큐에 넣었다가 모두 빼내는 연산과 매우 유사
  - 시간복잡도 O(ElogE)로 판단할 수 있음
  - 중복 간선을 포함하지 않는 경우에 이를 O(logV)로 정리
  - O(ElogE) -> O(ElogV^2) -> O(2ElogV) -> O(ElogV)!