[그래프] 다익스트라 최적화1

이전 글에서 소개했던 0-1BFS알고리즘과 함께 찾은 특정한 그래프에서 작동하는 다익스트라 알고리즘을 발견하게 되어서, 이 알고리즘도 소개를 합니다.

이 알고리즘을 이해하기 위해서는 다익스트라 알고리즘을 알고 있어야 합니다.

해결할 문제

주어진 문제는 다음과 같습니다.

그래프G에 V개의 정점과 E개의 간선이 있습니다.
모든 가중치 W들은 다음 식을 만족합니다.
W ∈ {X, Y}
X, Y ≥ 0
이 그래프에서 최단 경로를 구하세요.

Naive Solution : 기존의 다익스트라

대부분의 사람들은 이 문제를 접하면 O(ElogV)에 해결할 수 있는 다익스트라를 쓸 것입니다.
만약 피보나치 힙을 쓴다면, O(E+VlogV)에 해결할 수도 있습니다.
하지만, 이 문제는 선형 시간으로도 풀 수 있습니다.

Optimize Solution

기존의 다익스트라에 O(logV) 요소가 있는 이유를 살펴봅시다.
바로 우선순위큐(Priority Queue) 때문입니다.
만약 큐를 정렬된 상태로 유지하는 것을 항상 O(1)에 수행할 수 있다면,
우선순위큐를 일반적인 큐로 대체하고 시작점부터 모든 정점까지의 최단 경로를 찾을 수 있습니다.

먼저, QX와 QY 두 개의 큐를 만듭니다.
그리고, 여러분들은 u정점에 있고, 간선(u, v)를 통과해서 시작점으로부터의 최단 거리를 줄일 수 있다고 가정해봅시다.
만약, u에서 v로 가는 간선의 가중치가 X라면 QX에 넣고, Y라면 QY에 넣습니다.
따라서, QX에는 마지막으로 가중치가 X인 간선을 지나서 현재의 최단 거리를 얻은 모든 정점들의 정보가 저장되어있고, QY에는 마지막으로 가중치가 Y인 간선을 지나서 현재의 최단 거리를 얻은 모든 정점들의 정보가 저장되어 있습니다.

전체적인 알고리즘은 다익스트라 알고리즘과 거의 일치합니다.

달라진 점은,

앞에서 언급했던것 처럼 시간복잡도에서 log요소를 없애기 위해 우선순위큐 대신에 두 개의 큐를 사용합니다.
다익스트라는 항상 top node가 다음에 방문할 정점이지만, 이 알고리즘에서는 두 개의 큐의 헤드 중 더 가까운 정점을 다음에 방문합니다.

만약 큐가 항상 정렬되어 있다는 것을 증명한다면, 계산을 위해 항상 가장 가까운 정점을 선택하므로 다익스트라와 다르지 않게 됩니다.

이제, 큐가 항상 정렬되어 있다는 것을 증명해봅시다. (증명 부분은 원문의 방식을 필자가 약간 변경한 방식입니다.)
일단 이 것이 증명이 된다면, 전체 알고리즘은 구현의 관점에서 보면 아주 사소해 보일 것 이고, log요소를 제거하기 때문에 선형 시간으로 실행이 됩니다.

시간 복잡도 증명

명제 : QX와 QY는 항상 정렬된 상태이다.

증명 : 역전(최단 거리 값 변화)가 QX에서 발생했다고 가정해봅시다.
QX의 가장 뒤에 있는 정점을 v, 뒤에서 두 번째에 있는 정점을 u라고 합시다.
정렬이 되어있다는 것은 dist[u] ≤ dist[v] 라는 것입니다.
즉, dist[u] > dist[v] 이 거짓이라는 것을 증명을 하면 QX가 정렬되어 있다는것이 참이 됩니다.(귀류법)

두 정점 모두 마지막에 가중치가 X인 간선을 지났기 때문에, 이 거리를 dist[v]와 dist[u]에서 모두 뺄 수 있습니다.
pre(a) = dist[a] - X라고 합시다.
따라서 pre(u) > pre(v)입니다.

pre(u)와 pre(v)가 두 개의 큐 중 어딘가에서 왔다는 것이 틀림 없습니다.
두 개의 큐가 항상 정렬되어 있다고 가정을 했기 때문에 u, v는 같은 큐에서 올 수 없습니다.
그러므로 u, v는 서로 다른 큐에 있어야 합니다.
이 알고리즘은 두 큐의 헤드 중 최소값을 다음에 방문할 정점으로 취합니다.
QX에는 u, v 순서로 들어오기 때문에 pre(u) ≤ pre(v)가 되야 하는데, 이 때 위에서 말한 dist[u] > dist[v]이 거짓이 됩니다.
그러므로 QX는 정렬이 되어있는 상태입니다.

QY도 같은 방법으로 증명이 가능합니다.

의사 코드

queue QX, QY  
push start S to QX
while one of the two queues is not empty:  
  u = pop minimal distant node among the two queue heads  

  for all edges e of form(u, v) :  
    if dist(v) > dist(u) + cost(e) :
      dist(v) = dist(u) + cose(e);
      if cost(e) == X :
        QX.push(dist(v), v);
      else :
        QY.push(dist(v), v);

모든 0-1BFS 문제는 이 알고리즘으로 해결할 수 있습니다.

[출처] https://codeforces.com/blog/entry/43508

여기까지가 코드포스에 올라온 글의 번역입니다.
시간복잡도는 0-1 BFS 알고리즘과 동일하게 유도 가능합니다.