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

1. 최단 경로 문제란?

벨만포드 알고리즘을 다룬 여기 문서 참고

 

2. 다익스트라 알고리즘

- 하나의 시작점에서 도착점으로 가는 최단 경로를 찾는 알고리즘

- 간선이 음의 값을 가져선 안 된다

 

<pseudo code>

1. graph, weight, start 가 주어진다

2. start(자기 자신)까지의 거리는 0으로 상정한다

3. 모든 vertex 들을 queue에 넣고 반복한다

- queue에 들어간 v 중에서 가장 작은 값을 찾아 뽑는다

- 뽑힌 v에 대해서 relaxation 수행

 

2.1. 예제

초기화

 

현재 Q에서 가장 작은 값을 찾는다 --> $s$

 

$s$의 인접 노드 중에서 더 작은 $y$ 선택

 

 

$y$에서 relaxation 시행, 가장 작은 $z$ 선택

 

$z$에서 relaxation 시행, Q에서 가장 작은 $t$로 다시 돌아감

 

$t$에서 relax 시행했을 때 $x$로 가는 경로값이 업데이트 된다

 

2.2. 수행시간

배열로 구현한 경우   --->   $O(V^{2})$

힙으로 구현한 경우   --->   $O(V\log V+ E\log V)$ 

피보나치 힙으로 구현한 경우    --->   $O(V\log V+ E)$