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

 

 

Dijkstra(다익스트라) 알고리즘은 경로 알고리즘의 가장 기초가 되는 알고리즘이며 대표적인 최단 경로 탐색 알고리즘 중 하나입니다.

 

경로생성에 정답은 없겠지만 요즘 나와있는 대부분의 경로 생성 알고리즘들의 근간이 되는 알고리즘입니다. 

 

다익스트라 알고리즘은 특정 노드(좌표)에서 갈 수 있는 모든 노드(좌표)로의 최단 경로를 계산해 줍니다.

 

 

 

 

 

 

위의 그림은 다익스트라의 구조를 설명할 때 주로 드는 예시입니다.

 

다익스트라의 가장 큰 특징은 앞서 말했듯이 특정 노드에서부터 방문할 수 있는 모든 노드까지의 최단 거리를 구하는 것입니다.

 

 

 

 

 

 

 

만약 1번 노드를 현재 노드(좌표)로 설정했다고 가정해 봅시다.

 

1번 노드에서 방문할 수 있는 노드는 2, 3, 4번 노드입니다. 

 

이때 2,3,4번 각각의 노드를 방문할 때 드는 비용, 즉 3, 6, 7의 값은 거리 비용입니다. 

 

현재 노드에서 가까울수록 비용이 적게 측정됩니다. 

 

따라서 다음 노드는 가장 비용이 적게 측정된 2번 노드로 이동하게 됩니다. 

 

 

 

 

 

 

2번 노드로 이동한 후 다시 각 노드로 이동할 때 발생하는 경로 비용을 계산해 보면 

 

3번 노드로 갈 때 거리 비용이 1번 노드에서 측정했을 때 6이었지만 2번 노드로 이동 한 이후엔 3 + 1 즉, 비용이 4가 되었습니다.

 

따라서 3번 노드로 이동할 수 있는 최소 경로는 1 -> 3번 노드가 아닌 1 -> 2 -> 3이 되는 것입니다. 

 

따라서 다익스트라 알고리즘은 이런 식으로 각 노드를 방문하면서 최소 경로를 업데이트합니다. 

 

---

 

오늘은 경로 생성 알고리즘의 근간인 다익스트라 알고리즘에 대해 알아봤습니다.

 

저는 현재 로봇을 공부하고 연구하는 사람이라 다익스트라 알고리즘부터 다양한 알고리즘들을 공부하고 있습니다.

 

다음 글에서는 아직까지도 많이 활용되고 있는 Astar알고리즘에 대해 작성해 보겠습니다. 

 

첫 블로그라 많이 부족해도 읽어주셔서 감사합니다.