다익스트라 최단 경로 알고리즘

최단 경로 찾기

• 주어진 가중치 그래프에서 어느 한 출발점에서 또 다른 도착점까지의 최단 경로를 찾는 문제
• 다익스트라 최단 경로 알고리즘이 가장 대표적인 최단 경로 탐색 알고리즘 중 하나임

다익스트라 알고리즘

• 출발점으로부터 최단 거리가 확정되지 않은 점들 중에서 출발점으로부터 가장 가까운 점을 추가
• 그 점의 최단 거리를 확정하는 방식

Peseudo Code

ShortestPath(G,s)
입력: 가중치 그래프 G=(V,E), |V|=n, |E|=m
출력: 출발점 s로부터 (n-1)개의 점까지 각각 최단 거리를 저장한 배열 D

1. 배열 D를 INF로 초기화. 단 D[s]=0으로 초기화 
	-> 배열 D[v]에는 출발점 s로부터 점 v까지의 거리를 저장한다.
    
2. while (s로부터의 최단 거리가 확정되지 않은 점이 있으면)

3. 		현재까지 최단 거리가 확정되지 않은 각 점 v에 대해서 
		최소의 D[v]의 값을 가진 점 V_min을 선택하고, s로부터 점 V_min까지의
        최단 거리 D[V_min]을 확정
        
4. s로부터 현재보다 짧은 거리로 점 V_min을 통해 우회 가능한
	각 점 w에 대해서 D[w]를 갱신 --> 간선완화
    
5. return D

예제

• 이 방법을 반복하여 모든 점에 대해 최단 경로를 탐색한다.

• 결과

시간복잡도

• while 루프가 (n-1)회 반복되고, 1회 반복 할 때,
  - 수도 코드 3번 줄에서 최소 D[v]를 가진 점을 찾는데 $O(n)$ 소요
  - 배열 D에서 최솟값을 찾기 때문
  - D[w] 갱신하는데도 걸리는 시간은 $O(n)$이다.
• 따라서 $O(n^2)$ 소요된다.
• 하지만 최소 힙을 사용한다면 $O(nlogn)$ 소요