vertex 수 V, edge 수 E인 그래프에 대해

다익스트라 알고리즘은 그냥 짜면 O(V^2), priority_queue와 같은 힙을 쓰면 O((E+V)Log(V))라고 함

문제는 저 priority_queue의 수도 코드인데(위키백과 참조)


1 function Dijkstra(Graph, source): 2 dist[source] ← 0 // Initialization 3 4 create vertex priority queue Q 5 6 for each vertex v in Graph: 7 if v ≠ source 8 dist[v] ← INFINITY // Unknown distance from source to v 9 prev[v] ← UNDEFINED // Predecessor of v 10 11 Q.add_with_priority(v, dist[v]) 12 13 14 while Q is not empty: // The main loop 15 u ← Q.extract_min() // Remove and return best vertex 16 for each neighbor v of u: // only v that are still in Q 17 alt ← dist[u] + length(u, v) 18 if alt < dist[v] 19 dist[v] ← alt 20 prev[v] ← u 21 Q.decrease_priority(v, alt) 22 23 return dist, prev


마지막에 Q.decrease_priority는 C++에는 구현되어 있지 않음.

이진 힙에서 힙이 아닌 곳에 위치한 데이터를 수정해서 순위를 재조정하려면 일단 그 데이터를 찾아야 하는데 따로 위치를 저장하지 않을 경우 위치를 찾는데 O(V)의 시간복잡도가 걸림.

그 위치를 수정하는데는 O(logV)가 걸릴 것 같고.

이건 while loop안에 있으니 결국 O(V^2)이 되버림.


stack overflow에서도 관련 글이 있는데

https://stackoverflow.com/questions/9209323/easiest-way-of-using-min-priority-queue-with-key-update-in-c


크게 두가지 해결책으로 나눠짐.


1.

첫번째는 vertex, distance 쌍을 priority_queue에 넣되, decrese_priority는 건너뛰고 계속 새로운 쌍을 넣는 거임.

그리고 top pair의 distance가 현재 배열에 기록된 distance와 다르면 낡은 쌍이니 lazy deletion해주고 넘어가는 것.


이 해결책은 queue의 길이가 vertex 수보다 더 길어지게 되어 비효율적이라는 것.

낡은 pair는 보통 queue의 뒤쪽에 위치하게되니 삭제되는 경우가 드물고 큐의 길이는 점점 늘어남.

이진 힙에서 삽입과 삭제는 logN을 따르니까. 매우 느려지게 될 수 있음.


근데 생각해보니 길이가 어디까지 늘어날진 몰라도 최대 N^2까지 늘어난다 가정해도 log(N^2) = 2logN이니까 시간복잡도 자체는 그대로 일 것 같긴 함...

다만 공간 복잡도가 O(N)에서 O(N^2)으로 늘어나고,

내가 구현하고 싶은 vertex 100000급의 그래프에서는 queue의 길이가 메모리 할당이 불가능할 수준까지 길어질 가능성도 있음...


2.

두번째는 직접 저 기능을 구현하는 것임.

vector를 컨터이너로 쓰고 알고리즘 헤더의 make_heap, push_heap, pop_heap을 이용해서 구현.

근데 이러면 힙이 아닌 데이터 수정에 O(V)의 시간복잡도가 걸리고 결국 O(V^2)이 되서 힙을 쓰느니만 못하게 됨.


그리고 아래는 


3.

그외에 직접 생각해 본것은 이진탐색트리를 쓰는 건데, AVL트리를 쓸경우 삽입, 탐색, 변경에 모두 O(log(V))가 걸리니 목표로 하는 시간복잡도에 맞출 수 있을 것같음.

마침 직접 구현한 AVL Tree가 있긴 한데...


https://github.com/Markgraf-Oh/TreeStructures


이것저것 상속으로 구현하려는 욕심때문에 너무 쓰레기 같은 코드임.


4.

마지막은 그냥 포기하고 O(V^2)의 시간복잡도로 간단하게 구현하는 것임


요약

위의 1~4중 적합한 해결책을 추천해주셈..

그리고 3의 트리 자료구조의 AVL tree가 써먹을 만한지, 아니면 걍 새로 배열을 이용해서 구현하는 게 나은지 추천좀.