다익스트라 알고리즘 : 이미 결정된 노드의 인접 노드를 또 탐색하면 어떻게 될까요?

 이 글을 읽기 전에 잘못 구현된 다익스트라 글을 보고 오시는 것 추천드립니다. 저는 그 글을 읽으셨고, 그 글에 나온 저격 데이터가 어떠한 원리로 작성되었는지 30% 정도 이해했다는 전제 하에 진행하도록 하겠습니다. 보통 이 알고리즘을 구현하실 때 Priority Queue를 이용하는 경우가 많습니다. 저는 그것을 기준으로 작성하였습니다.

 

---

 min_cost와 where_is_from, visit와 con이 있습니다. 이 중에서 con은 graph를 구축하는데 쓰이는 자료구조 정도로 생각하시면 됩니다. C++의 STL에서 vector <vector <node>> con과 같습니다.

 

 

 min_cost를 inf로 초기화 합니다. 그리고, where_is_from을 -1로, visit를 false로 초기화를 합니다. 다음에 pq에 시작점을 넣는 로직이 있습니다. 30번째 줄이 그 역할을 합니다.

 

 

 이 구현. 어디서 많이 보셨을 겁니다. '잘못된 다익스트라' 코드에 나온 예시입니다. 여기서 핵심은 딱 2개입니다. pq에 어떤 값이 빠졌던지 간에 인접한 노드들을 탐색합니다. #1 을 수행합니다. 다음에 40번째 줄에 있는 조건 #2 에 따라서, pq에 넣을 수도 있고, 그 작업이 생략 될 수도 있습니다.

 

 뭐가 문제일까요? 우선 순위큐에 시작점으로부터 to까지 거리에 대한 정보가 여러개가 들어갔습니다. 이건 별 문제가 되지 않습니다. 그런데, to까지의 거리가 2다. 라는 정보가 있던, 3이라는 정보가 있던, to와 인접한 노드들을 모두 탐색한다는 것입니다. 최악의 경우, 저렇게 구현하면 복잡도가 어떻게 나올까요?

 

 

  0번에서 출발한다고 해 보겠습니다. 0부터 0까지의 최단 거리는 0입니다. 더 이상 pq에 들어가는 원소는 없으니, 다음 while 루프에 올 때, 0까지의 최단 거리가 0이라는 정보가 빠집니다.

 

 

 다음에 0과 인접한 1부터 n까지의 최단 거리에 대한 정보가 pq에 들어갑니다. 1까지 거리는 1, 2까지 거리는 3, ... , n까지 거리는 2n-1까지라는 정보가 말입니다. 36번째 for 블록은 그러한 일을 수행합니다. pq의 top에는 1까지 거리가 1이라는 정보가 들어 있습니다.

 

 

 이 상태에서, 2번부터 n번까지의 최단 거리가 갱신이 된다면, pq에 2부터 n까지에 대한 정보가 들어갈 겁니다. 어떻게 갱신해야 하는지 보겠습니다.

 

 

 1부터 2까지 1, 1부터 3까지 3, ... , 1부터 n까지 2n-3 간선을 추가하면 어떨까요? 1을 거쳐서 가는 경우에 2까지 최단 거리는 2로, ... , n까지 최단 거리는 2n-2로 갱신됩니다. 당연하게도 노란색으로 표시된 것들은 모두 pq에 넣어집니다. 그리고, 제가 말한 상황을 표로 나타내면 다음과 같습니다.

 

 아직 하늘색 부분은 0부터 최단 거리가 확정되지 않은 노드들입니다. 이 중에서 누적 거리가 제일 작은 정보는 2까지의 최단 거리가 2라는 정보입니다.

 

 

 그러면, pq의 top에 있는, 2까지 거리는 2이다의 정보가 빠집니다. 즉, 2까지의 min_cost가 확정됩니다.

 

 

 이 상황에서, 어떻게 넣어야 3번부터 n번까지 거리에 대한 정보가 pq에 중복해서 들어갈 수 있을까요?

 

 

 요런 식으로 간선을 주면 됩니다. 그러면, pq에 3번부터 n번까지가 또 다시 들어갈 겁니다.

 

 

 이런 식으로 n개, n-1개, ... , 1개 노드에 대한 최단 거리를 계속 업데이트를, 즉 E번 하게 되면 pq에는 총 E개의 정보가 들어갈 겁니다. 그리고, 이 E개의 정보에 대해서 최대 V번 돌려야 합니다. 그러면 이 상태에서 2에서 1로 향하는 1짜리 간선, 0으로 향하는 3짜리 간선이 추가로 있다면 어떨까요? 사실 방향만 다르고 가중치는 같은 그 간선들은 있던 없던지 간에 보라색 부분의 최단 거리에는 영향을 주지 않음을 알 수 있습니다.

 

 

 그러면 i에서 j로 가는 (i<j) 양방향 간선의 가중치를 2(j-i)-1로 두어도 문제가 없겠네요. 제가 제시한 알고리즘을 비효율적으로 만드는데 문제가 없다는 이야기입니다.

 

 

 

 이렇게 하면, 정보가 올라오는 E개에 대해서 인접한 V-1개의 노드를 봐야 하므로, 시간 복잡도는 O(EV)가 됩니다.

 

---

 최악의 경우에 EV가 되는 것은 알겠습니다. 문제는, 그 경우에 실행 시간이 EV에 비례하는지, E^2에 비례하는지, 아니면 거기에 logV가 추가로 붙는지입니다.

 

 다시 이 부분을 봅시다. #1은 pq에서 아이템을 뽑으면 무조건 돌아가는 부분입니다. #2가 continue가 걸리는 경우, 즉, 이미 알려진 누적 거리보다 cur를 통해서 가는 것이 더 크거나 같다면, pq에 인접한 것들을 넣지 않습니다. 그러면 #2 조건 때문에, pq에 들어가는 최대 정보의 수를 구해야 합니다. 쉽게 생각해 보겠습니다.

 

 

 어떠한 경로를 거쳐서 from, to 순서로 가는 것이 to까지 가는 최단 경로라고 해 보겠습니다. 빨간 선을 썼을 때, to에서 파란선으로 이어지는 정보들이 들어갈 겁니다.

 

 

 그러면 to에서 파란선으로 이어지는 정보는 1번보다 더 들어갈까요? 아닙니다. 이미 빨간선으로 오는 상황이 to까지의 최단 경로라고 확정이 된 상황입니다. 빨간선이 아닌 다른 선으로 to로 들어왔을 때에는 이미 기존에 알려진 '빨간 선으로 들어왔을 때 to까지 최단 경로' 보다는 크거나 같습니다. #1번 for loop에는 들어오겠지만, #2번에서 continue가 걸려버립니다. 그러면 우선순위 큐에 파란 간선을 추가하는 작업이 생략이 되어 버립니다. 쉽게 생각하는 방법은, 업데이트가 되면, pq에 들어왔다는 것을 보시면 됩니다. 즉, pq에 들어온 정보의 총 갯수가, pq에 의한 복잡도를 좌우한다는 것입니다.

 

 파란선이 실제로 pq에 들어오는 경우에는 이미 to가 pq에서 최초로 빠진, 단 1번에 대해서만 만들어 집니다. 따라서 최대 E개의 정보가 pq에 들어가므로, pq 연산에 의한 복잡도는 ElogV가 됩니다. 그리고 이 E개의 정보에 대해서 최대 V번의 탐색을 합니다.

 

 따라서 #1에 의한 복잡도는 EV입니다. logV << V이므로, 최종적인 시간 복잡도는 O(EV)가 됩니다. 흔히 알려진 O(ElogV)보다 비효율적이 된 이유는, 이미 이전에 최단 거리가 결정된 노드에 대해서 그것과 인접한 노드들을 또 탐색했기 때문입니다. 할 필요가 없는 작업을 계속 한 댓가는 매우 컸습니다.