[알고리즘] 다익스트라(시간복잡도, 특징, 구현방법)

특징 

다익스트라 알고리즘은 정점에서 정점까지의 최소 거리를 구하는 알고리즘이다

특징으로는 음의 간선을 포함하는 경우에는 계속 업데이트 되므로 최소 거리를 구할 수 없다.

이 경우는 다익스트라 알고리즘이 아닌, 벨만 포드 알고리즘으로 거리를 구한다.

 

사용하는 곳

인공위성, GPS, 네비게이션등 최단 거리를 구하고자 하는 곳에 사용된다.

 

시간 복잡도

다익스트라 알고리즘은 인접 행렬로 구현할 경우 O(N^2)

리스트인 경우 O(N*onN)이 된다

힙을 사용해야되기 때문이다.

 

구현방법

다익스트라는

1. 모든 정점까지의 거리를 무한대로 설정

2. 시작점 거리 0으로 초기화

3. Q에 삽입

4. 현재 정점과 연결 되있으며, 거리가 업데이트되는 경우 Q에 삽입

5. Q가 빌때까지 반복