다익스트라 알고리즘 (Dijkstra's Algorithm)

다익스트라 알고리즘이란

그래프에서 하나의 시작 정점(source)에서 다른 모든 정점까지의 최단 경로를 찾는 알고리즘

• 주로 가중치가 있는 그래프에서 사용
• 가중치가 음수인 경우에는 적용이 될 수도 있고 되지 않을 수도 있음
• 무방향 그래프, 방향 그래프에서 모두 사용 가능
• 최단 경로: 시작 정점에서 특정 정점까지 도달하는 경로 중 가중치의 합이 최소인 경로
• 우선순위 큐(Priority Queue)를 이용하며 현재까지 최단 경로가 확정된 정점을 기반으로 인접한 정점들을 점진적으로 탐색
  • 우선순위 큐를 사용하는 이유는 현재까지 발견된 가장 짧은 거리의 노드를 효율적으로 선택하기 위함
  • 우선순위 큐는 값이 작은 요소부터 꺼낼 수 있는 가료구조
  • 우선순위 큐에 (현재까지의 거리, 노드 번호) 저장 >> $O(E log V)$

1. 다익스트라 알고리즘의 동작 과정

1. 초기화
   • 시작 정점에서부터 각 정점까지의 거리를 기록할 배열 dist[] 생성
   • 시작 정점의 거리를 0으로 설정
   • 다른 모든 정점의 거리는 무한대로 초기화
     • 해당 정점까지의 경로를 발견하지 못했음을 의미함
   • 우선순위 큐(Priority Queue)를 생성하고 시작 정점을 큐에 삽입함
2. 정점 선택 및 거리 업데이트
   • 큐에서 가장 작은 거리를 가진 정점을 꺼내서 현재까지의 최단 경로를 확정
   • 해당 정점의 인접 정점들을 탐색하며 인접 정점까지의 새로운 경로가 기존에 있는 경로보다 짧으면 그 인접 정점까지의 최단경로를 갱신
   • 갱신된 인접 정점의 정보를 우선순위 큐에 삽입
3. 반복
   • 큐가 빌 때까지 2번의 과정을 반복
   • 모든 정점에 대한 최단 경로가 확정되면 알고리즘 종료

1-1. Relaxation (완화) 과정

if d[u] + c(u, v) < d[v]:
    d[v] = d[u] + c(u, v)

• d[u]: 시작 정점에서 정점 u까지의 최단 경로
• d[v]: 시작 정점에서 정점 v까지의 현재 알려진 최단 경로
• c(u, v): 정점 u에서 정점 v로 가는 간선의 가중치

더 짧은 경로가 발견되었을 때 그 경로로 최단 경로를 갱신하는 과정

2. 다익스트라 알고리즘의 시간 복잡도

1. 인접 행렬: $O(V^2)$
   • 그래프의 밀도가 높은 경우 적합
2. 우선순위 큐, 인접 리스트: $O((V+E)log V)$
   • 간선의 수가 적고 정점이 많은 희소 그래프