[Algorithm] 다익스트라 알고리즘 - 최단 경로 알고리즘 1 🏃🏃

다익스트라 알고리즘은 최단 경로 알고리즘 중에 가장 기초가 되는 알고리즘입니다. 🏃🏃

그동안 최단거리를 구할 때 죽어라고 BFS를 이용해왔으나(제일 재밌는걸요), 가중치가 있는 상황에서는 항상 풀이가 까다로웠습니다.

저는 이제까지 BFS의 다음 노드 탐색 과정에서 가중치가 더 적은 노드의 탐색을 단순히 '코드 상으로 더 위쪽에' 작성함으로서 먼저 탐색하도록 했습니다. 이는 나름 괜찮은 방법이였지만, 당연히 한계가 있었습니다. 이럴 때 사용 할 수 있는 것이 '최단 경로 알고리즘'입니다. 가중치가 더 적은 쪽을 우선적으로 탐색하도록 하는 알고리즘이죠. 

 

<대표적인 최단 경로 알고리즘 3가지>

1. 다익스트라 알고리즘: 가중치가 있는 그래프 탐색의 최단 경로 찾기. 셋 중에 가장 빠름!

2. 벨만-포드 알고리즘: 음수 가중치가 있는 그래프 탐색의 최단 경로 찾기.

3. 플로이드-와샬 알고리즘: 그래프 내 모든 노드들 간의 최단 경로 탐색. 즉, 모든 노드들에 대해 다른 모든 노드들로 가는 최단 경로를 빠르게 구할 수 있음. 

(각 알고리즘에 대한 링크가 맨 아래 있슴~)

 

최단 경로 알고리즘은 대표적으로 다익스트라 알고리즘,  벨만-포드 알고리즘, 플로이드-와샬 알고리즘이 있습니다.

이 세가지 알고리즘은 용도에 따라 다르게 쓰입니다. 기본적으로 최단 경로 알고리즘에서 '음수 가중치 간선'의 존재 여부는 꽤나 중요합니다. 음수 가중치가 존재하는 상황은 이미 지나간 시간을 되돌리거나, 쓴 돈을 되돌려주거나, 사용한 에너지를 충전하는 등의 상황이 있겠죠? 이렇게 음수 간선이 존재할 때 한가지 주의해야 할 점이 있습니다. 바로  '음수 사이클'의 존재 여부 입니다. 이동을 하는데 오히려 가중치가 줄어드는 사이클이 존재한다면.. 사이클을 돌 때마다 계속해서 가중치가 낮아지기 때문에, 제대로 된 최단 경로를 찾기 힘들겠죠? 그럴 때 이용하는 알고리즘이 벨만-포드 알고리즘입니다. 벨만-포드 알고리즘은 음수 사이클의 존재 여부를 파악할 수 있게 해주기 때문에, 음수 간선이 있을 때는 벨만-포드 알고리즘을 이용해야합니다. 한편, 다익스트라 알고리즘과 벨만-포드 알고리즘은 시작 노드에서 다른 노드로 가는 최단거리만을 파악합니다. 하지만 여러 노드에 대해 다른 노드로의 최단거리를 알고 싶다면 어떻게 해야 할까요? 물론 여러번의 다익스트라를 진행하는 방법도 있겠지만... 메모리나 시간 때문에 말도 안 되겠죠? 이럴 떄 이용할 수 있는 것이 플로이드-와샬 알고리즘입니다. 플로이드-와샬 알고리즘은 모든 노드들의 쌍 간의 최단거리를 빠르게 파악 해야 할 때 쓸 수 있습니다. 그럼 다익스트라를 쓰는 이유는? 최단 경로 알고리즘 셋 중에 가장 빠르기 때문입니다!

 

<다익스트라 알고리즘>

다익스트라 알고리즘은 BFS와 비슷하게 진행하되, 자료구조 큐(queue) 대신에 우선순위 큐(PRIORITY_QUEUE)를 이용합니다.

기존 queue를 이용한 BFS는 노드와 연결된 간선을 탐색 할 때, 단순히 연결된 순서대로 탐색합니다. 즉, 인접리스트로 구현 했을 때, 인접리스트에 입력된 순서대로 탐색하게 됩니다. 그 다음 방문 여부를 체크하는 배열을 이용해서 한번 탐색한 노드는 다시 탐색하지 않는 방식으로 진행됐었죠. 그러나 이럴 경우에 에는 '돌아가는게 빠른 경우'를 파악하기 힘듭니다.  목적지 노드를 향해 떠날 때, DFS에서는 가장 적은 노드와 간선을 방문하게 됩니다. 그러나 오히려 더 많은 노드나 간선을 거치는 것이 가중치 합이 더 낮은 경우가 있을 수 있다는 것입니다.

재밌자고 만들어봤는데 재미없네요

위의 그림 1의 경우를 보겠습니다. 노드 1에서 시작되고, 목적지는 노드 4라고 하겠습니다. 그리고 인접리스트 입력 과정에서 노드 1에 4번 노드와 2번 노드가 순서대로 들어왔다고 가정해봅시다. 이럴 경우 queue로는 4번 노드와 2번 노드가 순서대로 입력되고, 탐색을 마치게 됩니다. 더 짧은 경로인 1-2-3-4경로를 찾을 수 없게 되는 것입니다. priority_queue를 이용한다면, 이런 문제를 피할 수 있습니다. prioirity_queue는 입력을 받을 때마다 가장 큰 값 부터 작아지는 순서대로 원소를 정렬합니다. 이를 통해서 현재까지의 T와 연결된 노드들 중, 가중치가 가장 작은 노드를 우선적으로 탐색할 수 있게 됩니다. 

증지!증지!!

가장 큰 값 부터 정렬하는데 어떻게 가중치가 가장 작은 것부터 탐색합니까?? queue의 가장 뒤 부터 탐색해줘? 아닙니다^^. 우선 순위대로 정렬해주는 힙, priority_queue를 이용합니다! C++STL의 priority_queue의 경우에는 오름차순 정렬이기 때문에 내림차순으로 정의해 주려면 원소를 넣고 뺄 때, -1을 곱해서 넣어주면 됩니다.(애초에 내림차순으로 생성해 줘도 됩니다~)

10과 100이 들어간다면, 넣어줄 때 -10과 -100을 넣는 것이지요. 그러면 나올 때 자연스럽게 -10이 먼저 나오게 되겠죠? 여기에 또 -1을 곱해주면 됩니다. 이렇게 하면 손쉽게 작은 숫자부터 배열 할 수 있겠죠?

 

이를 통해 위에서 예시로 든 상황에서 먼저 입력된 1-4 경로를 무시하고 탐색을 진행 할 수 있게 됩니다. 그렇게 답을 찾은 뒤 1-4 경로는 무시합니다. 굳이 que안에서 1-4경로를 찾아서 지워주지는 않습니다. 너무 비효율적이고 어렵기 때문입니다. 대신 해당 노드까지의 최단거리를 따로 저장하는 배열을 만든 다음 더 큰 값이 입력될 때마다 무시해주는 방법을 사용하겠습니다. 구현은 아래와 같습니다.

마지막 노드 V, 시작 노드 S, 가중치 합이 도달 할 수 없는 어느 큰 값 INF,

노드간 연결 정보를 모아둔 인접리스트 vec, 시작점으로 부터 해당 노드까지의 거리를 담은 벡터 dist를 이용하였습니다.  vec은 pair<int, int>형식으로 첫 번째에 다음 진행 노드를 두번째에는 가중치를 넣어줬습니다.

일단 INF로 값을 초기화한, dist를 만들어줬습니다. 더 짧은 경로를 발견했을때 값을 초기화 해주기 위해서, 그리고 값이 INF인지 확인해서 해당 노드까지의 도달여부를 알 수 있기 때문에 INF로 값을 초기화 해줬습니다.

prioirty_queue의 선언이 중요한데, pair<int, int>타입으로 <가중치, 노드번호>를 넣어주었습니다. 이런 순서로 넣어주어야 큐가 가중치 값을 비교하여 정렬 할 수 있지요. 그리고 잊지 않고 가중치에 (-1)을 곱해서 넣어주었습니다. 작은 수 부터 정렬하기 위해서임을 위에서 언급했었죠. 나머지는 BFS중 방문여부를 기록하는 배열을 이용하지 않고, 최단거리를 기록해가며 나아가는 방식의 BFS와 비슷합니다. 방금 pop한 노드로의 진행이 원래 내가 알던 거리보다 짧을 경우 값을 초기화 해주고 아닐 경우에는 무시하는 방식입니다.

 

이렇게 해서 dist배열에는 출발지점에서 부터 어떤 지점으로의 최단거리가 저장되게 됩니다. 값이 INF라면 한번도 도달한적 없다는 뜻이겠죠? 아래 dist를 출력하는 과정은 이를 보여주고자 넣어봤습니다.

 

시간 복잡도는 어떻게 될까요? 노드의 갯수를 V, 간선의 갯수를 E라고 하겠습니다. 기존에 방문여부를 확인하는 배열을 사용하는 방식의 BFS와 달리, 최단거리가 초기화 되기만 하면 새로 노드들을 넣어줬습니다. 진짜 최악의 경우에는 간선의 갯수만큼 노드 탐색을 할 수도 있는 것이지요. 우선 순위 큐에 원소를 넣고 뺄 떄마다 정렬이 일어나니 Big-O표기법으로 O(log|E|)입니다. 이를 간선 갯수만큼 반복하므로... 시간 복잡도는 O(|E|log|E|)가 되겠습니다. 이 때 간선 갯수 E는 보통 V^2보다 작으므로 Big-O표기법상 O(|E|log|V|)와 같이 표현 할 수 있습니다.

 

이로서 다익스트라 알고리즘에 대한 설명을 마치겠습니다. 최단 경로 알고리즘은 종류도 다양하고 전부 재미있는 알고리즘입니다. 최하단 링크를 통해 다른 최단 경로 알고리즘도 학습해보세요!

읽어주셔서 감사합니다. 불꽃카리스마 진호우!^^였습니다. 

 

 

(해당 글은 알고리즘 문제해결 전략을 참고하여 작성했습니다.)

벨만-포드 알고리즘 - 최단 경로 알고리즘 2 🏃‍♀️🏃‍♀️ - 이진호.불로그.이름추천. 받수다. (tistory.com)

플로이드-와샬 알고리즘 - 최단 경로 알고리즘 3 🏇🏇 - 이진호.불로그.이름추천. 받수다. (tistory.com)