사용자 도구

사이트 도구


ps:단일_출발지_최단_경로

단일 출발지 최단 경로 (Single Source Shortest Path)

  • 사이클이 없으면 (트리) ⇒ 최단 경로 이전에, 그냥 경로가 하나밖에 없다. BFS든 DFS든 아무거나 쓰면 된다 O(V)
  • 가중치 없는 그래프의 경우 ⇒ BFS로 돌린다. O(V+E)
  • 가중치 있는 그래프의 경우
    • 가중치가 양수이면 ⇒ 다익스트라. O(ElogV)
    • 가중치가 음수도 있으면 ⇒ 벨만-포드. O(VE)

너비우선탐색 (BFS)

  • 모든 엣지와 모든 노드를 한번씩 방문하니까 O(V+E)이다
  • dense 그래프에서는 좀 더 효율적일 수 있는 구현법으로 다음 방법도 있다. 노드마다 연결된 모든 엣지를 방문해보고 unvisited 노드들에 대해서만 처리하는 것이 아니라, unvisited 노드들의 셋을 만들어 유지하면서 unvisited 셋에 있는 노드 중에서 엣지가 존재하는 노드들을 방문하는 식으로 구현하는 방식이다게. (출처: https://casterian.net/archives/1342)

다익스트라 알고리즘

  • 이론상 피보나치 힙을 쓰면 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라고도 불리는 방법을 쓴다. 자료구조로 덱을 사용해서, add연산을 할때 웨이트가 0일때는 push-front로, 웨이트가 1일때는 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이 매우 작으면 사용해볼만 할지도 모르겠다.

코드

관련 문제

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

토론

댓글을 입력하세요:
T B B U Y
 
ps/단일_출발지_최단_경로.txt · 마지막으로 수정됨: 2021/02/15 01:48 저자 teferi