데이크스트라 알고리즘 (Dijkstra's algorithm)

최신 트렌드(?)는 다익스트라가 아닌 데이크스트라 라고 읽는 것 같다만.. 참 적응이 안된다.. (호이겐스가 하위헌스로 바뀔때 느꼈던 당혹감?).. 원래는 그래서 좀더 입에 붙을때까지는 그냥 다익스트라로 쓰겠다고 했었는데. 그래도 이제는 의식적으로라도 표준 발음으로 바꿔 읽으려고 노력은 해야할 것 같다.
이론상 피보나치 힙을 쓰면 O(E+VlogV)이지만, 상수값이 너무 커서 실용적인 범위에서는 비효율적. 라이브러리에서 제공하는 바이너리 힙을 이용해서 decrease-key 연산 대신에 중복 값을 add해서 사용하는 방법으로 O(ElogV)에 푸는 것이 일반적이다. 바이너리 힙에 decrease-key 기능을 구현해서 사용하는 사람도 간혹 있는데, 어느정도 속도 향상이 있는듯 하다.
- 상용 라이브러리들에서는 페어링 힙을 사용해서 구현한 경우도 종종 있다. 바이너리 힙을 써서 구현한 버전이 더 많기는 하다.
기본적인 알고리즘이라서 조금만 검색해도많은 설명이 나오지만, 구현법과 거기에 따른 시간복잡도 계산에 관련해서 명쾌하게 정리된 곳을 찾기가 어렵다. 이론적인 옵티멀인 피보나치 힙 버전과, decrease-key를 지원하는 바이너리 힙 버전과, 일반적으로 구현하는 방식인 decrease-key를 지원하지 않는 바이너리 힙 버전등이 섞여있는 경우가 많다;; 그래서 내 방식으로 다시 정리해보겠다.
우선 다익스트라 알고리즘은, 다음 1번과 2번을 반복하는 알고리즘이다.
- 1. 아직 방문하지 않은 노드중 가장 가까운 노드를 찾는다
- 2. 그 노드와 인접한 노드들에 대해서 거리를 갱신한다.
1번은 |V|번 실행된다. 이때 필요한 연산은 extract-min 이다. 2번은 sum_i(|Edge from Vi|) = |E|번 실행된다. 이때 필요한 연산은 decrease-key이다.
그래서 총 시간복잡도는 n개의 원소가 들어있는 상태에서 extract-min의 시간복잡도가 Tem(n), decrease-key의 시간복잡도가 Tdk(n)일때 O(|V|*Tem(|V|) + |E|*Tdk(|V|))이다.
그러면 각종 구현 방식에 매칭시켜보면.
- 크기 |V|의 배열을 이용한 다익스트라 구현은, Tem은 O(n), Tdk는 O(1). 그래서 시간복잡도는 O(|V|^2 + |E|) = O(|V|^2)
- 피보나치 힙을 이용한 다익스트라 구현은, Tem은 O(logn), Tdk는 O(1). 그래서 시간복잡도는 O(|V|log|V| + |E|).
- decrease-key를 O(logn)에 처리하는 바이너리힙을 사용한 경우는 Tem과 Tdk 모두 O(logn). 시간복잡도는 O(|V|log|V| + |E|log|V|) = O(|E|log|V|)
그러면 일반적으로 구현하게 되는, decrease-key대신 add만 지원하는 바이너리 힙을 사용하는 경우는? decrease-key 대신에 add를 사용하는 경우에 대한 일반적인 분석을 먼저하자.
- 이때는, 자료구조에 저장될 수 있는 원소의 최대 갯수가 |V|개가 |E|개이다. 그래서 Tem이나 Tadd를 O(f(|V|)가 아니라 O(f(|E|))로 바꿔서 생각해야 한다, 그리고 1번 작업에서 extract-min을 한번 할때마다 항상 unvisited 노드가 찾아지는 것이 아니라, 이미 방문한 노드도 찾아질 수 있고 그 경우에는 무시하고 다시 extract-min을 반복해야 한다. 그래서 1번 작업으로 |V|개의 노드를 찾기 위해서는 extract-min을 최대 |E|번 해야 한다. 그렇게 생각하면 시간복잡도가 O(|E|*Tem + |E|*Tadd) = O(|E|*(Tem + Tadd))이다.
- cpp나 python 등에서 기본 제공되는 heap은 Tem과 Tadd가 모두 O(logn)이다. 그래서 시간복잡도가 O(|E|log|E|) = O(|E|log|V|)으로 쓴다. 이게 가장 흔한 다익스트라의 구현이다
- 그냥 BFS의 경우도 사실 다익스트라의 특수한 케이스라고 생각할수도 있다. 웨이트가 모두 일정하다보니, 그냥 일반적인 Queue에 enqueue를 해도 Queue가 정렬된 상태로 유지되어서, dequeue가 extract-min과 같은 역할을 하는 상황. 그렇게 따지면 Tem(=dequeue)과 Tadd(=enqueue)가 모두 O(1)이라서 총 복잡도가 O(|E|)가 되는 경우이다.
  - 물론 여기에서는 이미 한번이라도 visited한 노드에 대해서는 add를 할 필요가 없어서, 컨테이너의 원소 갯수가 최대 |E|개가 아니라 최대 |V|개지만, 지금 논의에서는 크게 중요치 않다.

특수한 형태의 그래프에 대한 최적화

양수 가중치를 갖는 그래프에서 최단경로를 구할때는 데이크스트라가 표준이지만.. 가중치 형태에 따라서 적용할수 있는 다른 방법들도 있다
엣지의 웨이트가 0 또는 1만 있을 때 - 0-1 BFS를 쓸수 있다. 0-1 BFS 참고. 자료구조로 덱을 쓰고, add는 push-front 또는 push-back으로, extract-min을 pop-front로 처리하므로, 결국 Tem과 Tadd가 모두 O(1)이고 총 시간복잡도는 O(|E|).
엣지의 웨이트가 2종류만 있을 때 - 다익스트라 최적화1 에서 소개하는 방법이 있다. 자료구조로 2개의 Queue를 사용해서, add연산을 할때는 웨이트에 해당하는 큐에 enqueue한다. 두 큐가 각각 정렬된 상태로 유지되므로 extract-min은 두개의 큐의 front값을 비교해서 더 작은쪽에서 dequeue한다. 이 경우도 결국 Tem과 Tadd가 모두 O(1)이므로 총 시간복잡도는 O(|E|).
엣지의 웨이트가 K종류만 있을 때 - 위의 출처에서는 언급된 적 없지만, 내가 쉽게 떠올려 본 일반화 방법이다. K개의 Queue를 사용하게 되고 add연산은 똑같이 O(1)이다. extract-min은 K개의 front 값중 최소값을 구해야 하니 O(K)인데. 각 큐의 최소값을 저장하는 heap을 따로 둔다면 O(logK)에도 가능할것 같다. 그렇다면 Tadd는 O(1), Tem은 O(logK). 총 시간복잡도는 O(|E|logK).
- ⇒ 실제로 구현해서 K=10인 문제에 시도해본 결과, 속도 향상이 별로 없었다. 그냥 이건 잊어버리자.
엣지의 웨이트가 N이하의 자연수일 때
- 사실 웨이트가 정수범위일때는 N에 바운드되는 알고리즘이 다익스트라 알고리즘 외에도 여러가지가 있는 듯 하다. 위키에 따르면 O(E+V*sqrt(logN))이나 O(EloglogN) 알고리즘이 최적이라고 한다. 그러나 아마도 ps에서 실용적으로 쓰이기 힘든 알고리즘일 가능성이 커보인다..
- 그나마 조금 설명을 찾기 쉬운 방법중에, 버켓큐라는 자료구조를 이용해서 다익스트라를 구현한 Dial's algorithm이란게 보인다. Dial's algorithm에 설명된 내용을 바탕으로 해보면, 거리의 최댓값이 되는 N*|V|개의 버켓을 만들어서, 각 노드를 그 노드까지의 거리에 해당되는 버켓에 담는다. decrease-key는 oldDist번째 버켓에서 Vi를 빼고, newDist번째 버켓에 Vi를 추가하는 거니까 각 버켓들을 hash-set으로 구현한다면 O(1)에 처리된다. V개의 노드에 대해 extract-min을 하는 것은 거리가 1인 버켓부터 거리가 N*|V|인 버켓까지 순회하면서 버켓 안의 원소를 찾는거니까 O(N*|V| + |V|)가 된다. 그래서 총 복잡도는 O(N*|V| + |E|) 가 되는 방법이다. 구현하기에도 복잡하지 않아보인다
  - ⇒ 그러나 이것도 실제로 구현해서 N=10인 문제에 시도해본 결과, 속도 향상이 별로 없었다. 이것도 그냥 잊어버리자.
- 다익스트라의 변형은 아니지만, 임시 노드를 추가해서 (길이 N짜리 엣지 사이에 N-1개의 임시 노드를 추가), 모든 엣지의 길이가 1인 그래프로 바꾼 뒤에 BFS를 적용하는 방법도 있다. 이해하기에 직관적이라는 것은 장점이지만, 시간적으로는 노드와 엣지가 O(|V|+N*|E|), O(N*|E|)인 그래프를 만든 뒤에 BFS를 돌리는 셈이니 O(|V|+N*|E|))가 된다. 시간복잡도 상으로는 위의 방법에 비해 비효율적이고 그냥 다익스트라의 O(|E|log|V|)랑 비교해도, |N|이 log|V|보다 작아야 메리트가 있을것 같다. N이 매우 작으면 사용해볼만 할지도 모르겠다.
그래프가 Dense할때 - 이건 사실 최적화라기 보다는 이쪽이 가장 오리지널 다익스트라 알고리즘인데.. 힙을 안쓰고 그냥 O(V^2)에 구현할수 있다. 보통은 O(ElogV)가 빠르겠지만, E가 V^2에 가까울정도로 dense하다면 이쪽이 더 효율적일수 있다.
- 특정한 최단 경로에서 시도해봤는데.. 더 빨라지지는 않았다. 메모리는 좀더 줄었다.

코드

teflib.graph.dijkstra

기타 등등

세그트리 기반의 구현법
- PyRival에서 처리되지 않은 pull request중에서, 데이크스트라 구현을 세그먼트 트리 기반으로 바꾸려는 리퀘스트가 있다.
- 근거는 python의 heapq에 튜플을 원소로 넣을때 너무 느리기 때문에 heapq기반 데이크스트라로는 풀수 없는 codeforce 문제들이 있다는 것이다.. 그래서 제안하는 방법은 heapq 대신에 min segtree를 사용하는 것.
- 아니 근데.. min seg tree를 아무리 열심히 구현해도 heapq랑 비교가 안되게 느린데.. 아무리 (1)tuple을 안써고 되고, (2)add 대신에 decrease-key 연산을 바로 사용할수 있다고 해도 정말 최종적으로 빨라지는게 맞나..?? 게다가 이렇게 되면 min값을 갖는 노드를 찾는것이 O(1)에서 O(logV)로 증가하는 셈인데?
- 속는셈 치고 한번 해봤다.. 최단경로 에 적용해서 풀어봤는데 역시나 속도가 더 느려졌다. (python 3.11)
  - 세그기반 구현 : 920ms
  - 세그기반 구현에 약간 최적화 (slot등을 사용해서): 832ms
  - heapq기반 표준 구현 (teflib) : 612ms

목차

데이크스트라 알고리즘 (Dijkstra's algorithm)

특수한 형태의 그래프에 대한 최적화

코드

관련 문제

기타 등등