정의

BFS와 다르게 가중치가 있는 가중치 그래프에서 단일 시작점으로부터 다른 모든 정점까지의 최단 경로를 구하는데 사용되는 알고리즘

특징

1. 탐색 방식
   • 시작 정점에서 출발하여, 점진적으로 가장 가까운 정점으로 이동하여 최단 거리 갱신
   • 그리디 알고리즘을 기반으로 동작
2. 적용 조건
   • 그래프의 간선 가중치가 0 이상이어야 함
   • 방향 그래프나 무방향 그래프 모두에 사용 가능 (중요!)
3. 시간 복잡도
   • 인접 리스트와 우선순위 큐를 이용하면 O((V + E)log V), V : 정점 수, E : 간선 수 (가능하다면 우선순위 큐를 이용해서 풀자!)
   • 인접 행렬을 사용하면 O(V*V)
4. 제한 사항
   • 음수 간선이 있는 그래프에서는 사용할 수 없음 (이때는 벨만-포드 알고리즘을 사용해야 함)

동작 과정

1. 초기화
   • 시작 정점의 거리를 0으로 설정하고, 나머지 정점의 거리를 무한대로 설정
   • 방문하지 않은 정점을 모두 포함한 집합 생성
2. 탐색 반복
   • 방문하지 않은 정점 중 가장 거리가 짧은 정점을 선택
   • 해당 정점에서 갈 수 있는 인접 정점의 거리를 계산하고, 기존 거리보다 짧으면 갱신
   • 해당 정점을 방문 처리
3. 종료 조건
   • 모든 정점을 방문하거나, 더 이상 최단거리를 갱신할 수 없을 때 종료

장점

• 최단 경로를 효율적으로 구할 수 있음
• 간단한 구현으로 다양한 문제에 적용 가능

단점

• 음수 간선을 처리할 수 없음
• 큰 그래프에서는 메모리와 시간 복잡도가 증가