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

• 이 글은 (https://m.blog.naver.com/ndb796/221234424646) 블로그 글을 참고하여 작성하였습니다.

다익스트라 알고리즘

다이나믹 프로그래밍(DP)을 활용한 대표적인 최단 경로 탐색 알고리즘입니다. 기본적으로 다익스트라는 하나의 최단 거리를 구할 때 이전에 구했던 최단 거리를 사용한다는 특징때문에 다이나믹 프로그램을 활용한다고 볼 수 있습니다.

1. 출발 노드를 설정합니다.
2. 출발 노드에서 각 노드까지 가는 최소 비용을 배열을 만들어 저장합니다.
3. 방문하지 않는 노드 중에서 가장 비용이 적은 노드를 선택합니다.
4. 해당 노드를 거쳐서 각 노드로 가는 경우까지 비교하여 최소 비용을 갱신합니다.
5. 위 과정에서 3~4번 반복합니다.

여기서 3번 과정에서 코딩 구현 시 배열을 완전 탐색해서 최소 비용 노드를 선택하는 방법이 있고, 우선순위 큐를 활용하여 최소 비용 노드를 선택하는 방법이 있습니다. 저는 우선순위 큐를 활용한 방법에 대해 소개해드리겠습니다.

위와 같은 그래프는 실제로 컴퓨터에서 표현할 때는 이차원 배열로 표현해야 합니다.
1번 노드를 출발 노드를 설정을 하게 되면 해당 노드부터 각 노드까지 거리를 다음과 같이 1차원 배열로 표현합니다.

1번 노드를 제외한 노드 중 방문하지 않는 노드 중 가장 비용이 적은 노드를 선택해야 합니다. 가장 최소 비용을 계속 계산하는 것보다는 우선순위 큐를 두어 비용이 최소가 되는 노드를 자동으로 선택할 수 있게 구현을 하면 좀 더 쉽게 구현할 수 있습니다.

남은 노드들 중에서 가장 최소 비용 노드를 선택합니다. 따라서 우선순위 큐를 고려하여 3번 노드가 선택되었습니다. 4번 노드를 거쳐서 가는 경우를 모두 고려하여 최소 비용 배열을 갱신하면 됩니다.

원래 노드1에서 노드5까지 가는 비용은 INF 였습니다. 하지만 노드 3을 거쳐서 가는 비용은 3이므로 3으로 갱신합니다. 결과적으로 최소 비용 배열은 다음과 같습니다.

우선순위 큐는 다음과 같이 갱신이 되고 이제 다음 최소 노드인 2를 거쳐서 가는 비용을 모두 갱신하는 방식으로 반복하면 됩니다.

원래 노드1에서 노드4까지 가는 비용은 4 였습니다. 하지만 노드 2를 거쳐서 가는 비용은 3이므로 3으로 갱신합니다. 결과적으로 최소 비용 배열은 다음과 같습니다.

이와 같은 방법으로 반복하다 보면 최소 비용 배열을 완성시킬 수 있습니다.

코드

• 추가로 궁금한 점이나 수정할 부분 있으면 댓글로 남겨주세요.