최단 경로(Shortest path) 문제
: 가중치 그래프의 임의의 출발점에서 다른 도착점까지의 최단 경로를 찾는 문제
다익스트라 알고리즘
- 모든 정점을 경로가 확정된 점들 & 미확정된 점들로 구분
- 알고리즘의 1단계 수행 시 경로가 미확정된 점 1개 선택하여 그 점의 경로를 확정
알고리즘
step 1. 경로가 미확정된 점 중 출발점에서 가장 가까운 점 선택
- 선택된 점을 m이라 하자
- 프림 MST 알고리즘에서 트리를 들어 올려 가장 짧게 매달린 단추 선택하는 거랑 같음
step 2. 확정된 점에 대해 간선 완화(edge relaxation)
m에 인접하면서 경로가 미확정된 점 에 대해 거리 계산 수행
-> 출발점에서 m을 거쳐서 인접한 점에 도달한 거리가 더 가까운 경우에만 그 거리를 기록함
수행시간
초기 시작점부터 총 n회 최단 경로가 확정된 정점(단추)들을 들어 올려 점 1개씩 최단 경로 확정시킴
- 정점의 최단 거리 확정 시 미확정된 점 중에서 시작점에서 가장 가까운 점 찾음 => O(n)시간
- 간선 완화 : O(n)시간
=> 수행시간 : n x (O(n)+O(n)) = O(n^2)