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

안녕하세요 이번에 포스팅할 내용은 학부과정 알고리즘 시간에 배웠던 다익스트라 알고리즘 입니다.

 

먼저 다익스트라 알고리즘은 주어진 그래프에서 Greedy 기반으로 최적의 경로를 탐색하는 알고리즘 입니다.

 

Greedy 란?

Greedy 란 탐욕알고리즘으로 매 주어진 상황에서 가장 좋은 경로를 선택함으로써 만들어가는 탐색 방법입니다.

예를 들어

 

위와 같이 Start 지점에서 갈 수 있는 경로의 비용을 비교했을 때 가장 낮은 2를 선택합니다.

그리고 Zero-base로 다음노드에서는 현재 갈 수 있는 경로의 비용만 가지고 최선의 비용을 선택하기 때문에 5와 7중 비용이 적은 5를 선택하고 END 노드에 도착할 수 있습니다.

 

이렇게 매 순간 가장 최선의 방법만을 선택해서 나아가는 방법을 Greedy 알고리즘이라고 합니다.

그리고 이런 Greedy 알고리즘을 이용해서 다익스트라 일고리즘이 작동된다는 것!은 아래 다익스트라 설명을 통해 충분히 이해하실 수 있습니다~!

 

1. 동작 과정

그럼 본격적으로 예시를 통해 다익스트라 알고리즘에 대한 포스팅을 진행하겠습니다.

위와 같이 처음 시작 노드를 3으로 가정하고 알고리즘을 적용하겠습니다.

먼저 가장 처음 각각의 노드에서 이동할 수 있는 비용은 모두 Infinity로 설정합니다. (물론 시작지점인 3은 바로 0으로 값을 초기화 시켜도 괜찮습니다.)

 

 

이 후 3번 노드에서 이동 가능한 2번노드와 4번노드의 비용을 각각 현재 배열에 저장된 값과 비교하여 최솟값을 선택합니다.

min(arr[2(노드번호)],12)와 min(arr[4],5)를 각각 비교하면 현재 배열에 저장된 값이 infinity 값이기 때문에 아래와 같이 배열을 수정할 수 있습니다.

 

그리고 2번노드와 4번노드 중 최소 비용이 걸리는 4번노드로 이동 후 같은 작업을 반복합니다.

 

4번노드의 경우 1번노드와 2번노드로 이동할 수 있기 때문에 min(arr[1],arr[4]+1)과 min(arr[2],arr[4]+7)을 통해 배열을 수정합니다.

위와 2번 노드로 이동하는 비용은 12로 같기 때문에 변화가 없고 1번노드로 가는 비용은 무한대보다 6이 더 최솟값이기 때문에 위 배열 값을 수정됩니다.

마찬가지로 1번노드로 이동 후 작업을 반복 합니다. 이 때 min(arr[1]+3,arr[2])를 비교하고

결과적으로 위와 같이 2번노드에 최소비용 값이 수정 되는 것을 알 수 있습니다.

마찬가지로 2번노드로 이동 후 같은 작업을 반복하는데 이 때 2번노드에서 이동할 수 없는 화살표가 없기 때문에 작업이 일어나지 않습니다.

또한 모든 노드를 방문하면 다익스트라 알고리즘이 끝나기 때문에 위 정리된 최소비용배열을 구함으로써 다익스트라 알고리즘이 종료됩니다.

 

2. 효율성

 

다익스트라 알고리즘의 효율성을 알아보면 먼저 최악의 경우 N개의 노드가 있을 때 첫 번 째 노드에서 N-1번의 연산이 일어나고

2 번째 노드에서도 N-1번의 연산이 일어납니다.(화살표가 양방향으로 있는 경우 고려)

즉 결과적으로 N*(N-1)의 연산이 일어나고 최악의 경우 O(N^2)의 효율성을 가지게 됩니다.

 

 

하지만 만약 최소비용을 저장하는 방법이 배열이 아닌 우선순위 큐를 이용했다면 효율성을 조금 더 높일 수 있습니다.

다익스트라 알고리즘의 경우 매 순간 최솟값을 비교를 통해 구하고 최솟값을 바탕으로 갱신하며 진행되기 때문에 우선순위 큐를 이용하여 구현하게 되면

최솟값을 선택하는 비용이 상수 비용이 되기 때문에 효율성을 높일 수 있습니다.

 

결과적으로 노드가 N개 있고 간선의 갯수가 E개 있다면 우선순위 큐 높이가 logN이 되고 이 때 우선순위큐에 새로운 데이터를 삽입 및 삭제하는 과정은 최악의 경우 E개수 만큼진행되므로 O(ElogN)의 효율성을 가지게 됩니다.

단, 이 경우역시 최악의 경우 E의 개수는 O(N^2)과 같으므로 최악의 경우 O(N^2logN)의 극악 효율성을 가지게 됩니다.

 

마지막으로 다익스트라의 가장 큰 단점은 비용이 양수가 아닌 음수의 경우 무한 루프에 빠지는 등 결과 값을 제대로 구할 수 없는 치명적인 단점을 가지고 있습니다. 때문에 다익스트라의 변형을 통해 문제를 해결하는 벨만-포드 알고리즘이 존재하고 있습니다.

그래서 다음에는 벨만-포드 알고리즘 포스팅을 주제로 진행하겠습니다.

 

감사합니다.