다익스트라(Dijkstra)란 무엇인가?

▏목적

 

      ◦ 다익스트라 알고리즘 이해하기

 

 

 

▏시작하는 말

 

프로그래머스에서 "배달"이라는 문제를 풀어보았는데, 이런 유형의 문제는 처음 접해봐서 그런지 어떻게 풀어야 할지 감조차 오지 않았다. 그래서 구글에서 여러 알고리즘들을 살펴보다 최단거리를 구하는 다익스트라를 알게 되었다. 이 방법이라면 이 문제를 해결 할 수 있을 것 같아 다익스트라를 충분히 이해하고, 다시 풀어보았는데 손쉽게 풀었다.

완벽히 다익스트라를 알게된 지금, 내가 직접 문제를 만들어 설명해보려 한다. 

 

 

 

▏다익스트라(Dijkstra) 란 무엇인가?

 

다익스트라는 최단거리를 탐색하는 방법이다. 쉽게 말해 특정한 한 점에서 다른 모든 점까지 가는 경로의 최소를 구하는 것이다.

 

이것의 가장 큰 특징은 한 점 까지의 최단거리를 구할 때 그 전까지 구한 최단거리를 이용한다는 점이다.

 

 

 

▏원리

 

  1. 모든 점의 거리를 무한으로 초기화 한다.

 

 

 

2. 시작점인 점1에서 갈 수 있는 점들의 거리, 즉 연결된 노드의 가중치를 갱신시켜 준다.

 

 

 

3. 가장 작은 값의 노드를 방문한다.

     예시의 경우 최소거리인 점2로 경로를 확정한다.

 

 

 

  4. 방문한 곳에서부터 연결된 노드들의 가중치를 갱신한다. ( 2-3 과정 반복 )

 

 

 

  5. 방문 할 수 있는 점들 중 최단거리인 점4로 경로를 확정하고, 새롭게 방문 할 수 있는 거리를 갱신해준다.

 

 

 

  6. 방문 할 수 있는 경로들 중 최단거리인 점5로 경로를 확정하고, 점3으로 갈 수 있는 거리를 갱신시켜준다.

 

 

 

  7. 1 > 2 > 5 > 3 이 최단 거리이므로 점3의 거리는 4로 확정된다.

 

 

 

 

 

▏정리

 

 

1. 모든 점들의 거리를 무한으로 초기화한다. 

2. 출발점과 연결된 노드들의 가중치(거리)의 값을 변환한다.  

3. 갈 수 있는 점들중 가장 작은 가중치(거리)를 찾아 경로를 확정한다.

4. 확정한 경로에서 갈 수 있는 점들의 거리를 다시 갱신시켜준다.

5. 3-4 를 반복하면 된다.

 

 

다음 포스팅 에서는 JAVA 코드로 직접 구현해보겠습니다.

 

 

 

▏참고자료

 

https://matice.tistory.com/56