그래프에서 한 정점에서 다른 모든 정점으로 가는 최단 경로를 구하는 알고리즘
음의 가중치가 없는 그래프에서만 정상적으로 작동
네트워크 경로 탐색, 지리적 위치 간 최단 거리 계산 등에서 사용한다.
-초기화
출발 정점에서의 거리는 0으로 설정하고, 나머지 모든 정점의 거리는 무한대로 설정한다.
방문한 정점은 없으므로 모든 정점을 미방문 상태로 둔다.
-최단 경로 찾기
현재까지 방문하지 않은 정점들 중 출발 정점으로부터의 거리가 가장 짧은 정점을 선택한다.
선택한 정점을 "방문 완료"로 표시하고, 해당 정점에서 갈 수 있는 인접한 정점들의 거리를 업데이트한다.
즉, 해당 정점까지의 거리 + 간선의 가중치가 기존에 기록된 거리보다 짧으면 값을 업데이트한다.
모든 정점이 방문될 땨까지 해당 과정을 반복한다.
종료 조건
모든 정점이 방문되면 알고리즘이 종료되며, 각 정점에 대한 최단 경로를 알 수 있다.
시간 복잡도
우선순위 큐를 사용하여 구현할 경우 시간 복잡도는 O(ElogV)이며, E는 간선의 수, V는 정점의 수이다.