[알고리즘] 다익스트라 알고리즘(데이크스트라 알고리즘)

다익스트라 알고리즘?

 

다익스트라 알고리즘은 1956년 컴퓨터 과학자 에츠허르 데이크스트라가 고안한 그래프에서 노드 간 최단 경로를 찾는 알고리즘이다. 

이때 노드 간 거리(혹은 가중치 등)가 음수인 경우는 다익스트라 알고리즘을 사용할 수 없다.

 

원래는 두 노드 간 최단 경로를 찾는 알고리즘이였다.

그러나 한 노드를 고정하고 해당 노드로부터 다른 노드들 까지의 최단 경로를 찾는 변형된 버전도 있다.

이 버전이 현재로써는 더 일반적이다.

따라서 나 또한 변형 버전을 중심으로 조사하였다.

 

이제 탐색 방법을 확인해 보자면

 

• 과정 1

우선 한가지 노드를 시작점으로 잡는다. (시작점 노드는 당연히 거리가 0이다.)

나머지 노드는 전부 거리가 무한대라고 가정한다.(아직 탐색을 하지 않았으므로...)

 

• 과정 2

이제 시작점 노드와 연결된 노드들을 탐색한다.

탐색한 노드들에 해당 노드에 가기 위한 거리(혹은 비용, 가중치 등등..)를 저장한다.

 

• 과정 3

그 다음 현재까지 탐색된 노드들(=저장된 거리가 무한대가 아닌 노드) 중에서 (탐색이 완료된 노드를 제외하고. 즉, 과정 2와 같은 과정을 거친 노드를 제외하고) 가장 저장된 거리가 짧은 노드를 선택한다. 

과정 2에서 진행한 것 처럼 선택한 현재 노드와 연결된 노드들을 탐색한 후 해당 노드에 가기 위한 거리(현재 노드에 저장된 거리+현재노드에서 탐색한 노드에 가기 위한 거리. 즉, 시작점~탐색한 노드 거리)를 저장한다.

 

• 과정 4

과정 3의 과정을 모든 노드가 탐색이 완료될 때 까지 진행한다.

 

결과적으로 각 노드에 저장된 값이 시작점에서 해당 노드까지의 최단 거리이다.

 

이해를 돕기 위한 자료(출처: 위키백과)

 

다익스트라 알고리즘 시간 단축

노드의 개수가 V일 때, 다익스트라 알고리즘의 시간복잡도는 O(V^2)이다.

우선순위 큐를 이용하면 이를 개선할 수 있다.

 

우선순위 큐는 기존의 큐와 같이 선입선출 방식의 자료구조와는 다르게 우선순위를 부여해서 우선순위에 따라서 자료를 꺼내는 자료구조이다.

 

위의 (과정 3)에서 현재까지 탐색된 노들들 중에서 가장 저장된 거리가 짧은 노드를 찾는 단계를 진행할 때 이를 이용할 수 있다.

 

큐에 탐색할 노드를 저장할 때 (거리, 노드번호)로 저장하면 거리가 짧은 노드가 우선적으로 추출된다. 이를 통해 모든 노드를 검사하여 최소값을 지닌 노드를 찾는 과정을 더 빠른 방법으로 대신할 수 있다.

 

마무리

다익스트라 알고리즘은 최단경로라는 백준 문제를 풀던 중 알게된 알고리즘이다.

 

처음엔 다익스트라 알고리즘에 대해 몰라서 시간초과가 계속 났다.

알고리즘 분류의 데이크스트라라는 키워드를 보고 조사를 해본 후에야 감이 잡혀서 풀 수 있었다.

 

네비게이션같은 길찾기 시스템에 쓰이기 때문에 관련 프로젝트를 진행할 때 활용해보면 좋을 것 같다.

 

 

 

 

자료 조사 출처

데이크스트라 알고리즘 - 위키백과, 우리 모두의 백과사전

 

23. 다익스트라(Dijkstra) 알고리즘

 

최단 경로_다익스트라 & 우선순위 큐