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

다익스트라(Dijstra) 알고리즘은 그래프의 시작 노드에서 최종 목표 노드로 가기 위해 최단 경로를 구하는 알고리즘 이며, 최단 경로 탐색 알고리즘(Shortest Path) 이라고 부른다. 이 과정에서 오직 도착 노드 뿐만 아니라 다른 노드의 경로들을 방문하여 최단 경로를 찾아낸다. 이러한 목적을 달성하기 위해 매번 최단 경로의 노드를 탐색하기 된다.

 

동작 단계

1. 출발 노드를 설정한다.

2. 출발 노드를 기준으로 각 노드의 최소 비용을 저장한다.

3. 방문하지 않은 노드 중에서 가장 비용이 적은 노드를 선택한다.

4. 해당 노드를 거쳐서 특정한 노드느로 가는 경우를 고려햐아 최소 비용을 갱신한다.

5. 위 과정에서 3번 ~ 4번을 반복한다.

 

다익스트라는 일명 그리디 알고리즘 분류에 속하며, 최소 거리에 최소 거리를 붙어가면 최종적으로 최단거리를 계산할 수 있다는 논리를 기반으로 동작한다. 이것은 상황에 따라서 단점이 될 수 있는데, 코드 구현에 따라서 단순한 선형 탐색으로 찾게 된다. 빠르게 작동되어야 하는 경우에서 상황에 따라(정점의 갯수가 많고 간선은 적을 때) 치명적인 시간 지연이 될 수 도 있음을 유의해야 한다.