사용자 도구

사이트 도구


ps:다익스트라_알고리즘

다익스트라 알고리즘 (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하다면 이쪽이 더 효율적일수 있다.

엣지 웨이트가 동적으로 변할때?

  • 엣지의 거리가 동적으로 변하는 경우들을 생각해보자.
  • u→v 로 가는 거리가, u까지의 거리에 따라서 달라지는 경우
    • u까지 오는데 걸린 거리가 d일때, u→v 의 거리가 w[d] 라고 하면, d1⇐d2일때 d1+w[d1]⇐d2+w[d2] 를 만족시킨다면 여전히 최단 경로를 찾을수 있다.
    • 관련 문제: 국왕의 방문

코드

관련 문제

    • 엣지의 가중치가 10 이하의 자연수라서, 표준 다익스트라 외에도, “엣지의 웨이트가 K종류만 있을 때” 에 설명한 방법이나, “엣지의 웨이트가 N이하의 자연수일 때”의 방법을 테스트 해보기에 적당하다. 물론 위에서 언급했든 결과는 별로 안좋았다. 아주 소폭 빨라지거나 아니면 더 느려지거나..
    • 그래프가 dense한 편이라서 O(V^2) 구현을 테스트해보기에 적당하다.

토론

댓글을 입력하세요:
F S​ P I​ K
 
ps/다익스트라_알고리즘.txt · 마지막으로 수정됨: 2022/09/22 07:24 저자 teferi