Ch 4-4. 최단 경로

최단 경로(Shortest path) 문제

: 가중치 그래프의 임의의 출발점에서 다른 도착점까지의 최단 경로를 찾는 문제

다익스트라 알고리즘

• 모든 정점을 경로가 확정된 점들 & 미확정된 점들로 구분
• 알고리즘의 1단계 수행 시 경로가 미확정된 점 1개 선택하여 그 점의 경로를 확정

알고리즘

step 1. 경로가 미확정된 점 중 출발점에서 가장 가까운 점 선택

• 선택된 점을 m이라 하자
• 프림 MST 알고리즘에서 트리를 들어 올려 가장 짧게 매달린 단추 선택하는 거랑 같음

step 2. 확정된 점에 대해 간선 완화(edge relaxation)

m에 인접하면서 경로가 미확정된 점 에 대해 거리 계산 수행
-> 출발점에서 m을 거쳐서 인접한 점에 도달한 거리가 더 가까운 경우에만 그 거리를 기록함

• Go to step [1]

수행시간

초기 시작점부터 총 n회 최단 경로가 확정된 정점(단추)들을 들어 올려 점 1개씩 최단 경로 확정시킴

• 정점의 최단 거리 확정 시 미확정된 점 중에서 시작점에서 가장 가까운 점 찾음 => O(n)시간
• 간선 완화 : O(n)시간

=> 수행시간 : n x (O(n)+O(n)) = O(n^2)