0 - 1 너비 우선 탐색

들어가며..

다익스트라 알고리즘(Dijkstra's algorithm)을 이용하면 \(O(|E|+|V| \log(|V|))\)에 단일 출발지 최단 경로를 구할 수 있습니다. 만약, 간선의 가중치가 0 혹인 1 뿐이라면 더 빠르게 작동시킬 수 있을까요?

 

0 - 1 너비 우선 탐색

0 - 1 너비 우선 탐색은 다익스트라 알고리즘과 완전히 같은 아이디어로 작동합니다.(사실 0 - 1 너비 우선 탐색은 다익스트라 알고리즘을 최적화 한 것입니다.) 그저 가중치가 0 혹은 1 밖에 없는지라 priority queue를 사용하지 않을 수 있다는 것이 차별점이라 할 수 있겠습니다.

 

다익스트라에서 priority queue는 현재 queue에 들어있는 정점 중 시작 점으로 부터 가장 가까운(=현재 구한 최단 경로가 가장 짧은)정점을 우선적으로 확인하기 위해 이용합니다. 하지만, 그래프의 가중치가 0 또는 1 뿐이라면, 가중치가 0인 간선을 이용했을 경우에 반드시 가중치가 1인 간선을 이용했을 때보다 가까워 진다는 사실을 알 수 있습니다. 가중치가 0인 간선을 이용한 곳 부터 탐색을 진행해 주면 된다는 것을 의미합니다.

 

따라서, priority queue 대신 deque을 이용하여 가중치가 0인 간선을 이용했다면 front에 push해주고, 가중치가 1인 간선을 이용했다면 back에 push해주면 됩니다.

 

나머지는 다익스트라와 같게 작동합니다.

 

 0-1 BFS가 Dijkstra's algorithm과 동일하게 작동한다는 것을 보이기 위해서는 출발지로 부터 vertex까지의 distance가 deque 내에서 오름차순으로 정렬되어 있다는 것을 보이는 것 만으로 충분합니다. 0-1 BFS에서는 edge의 weight가 1인 경우에는 deque에 push back하고 0이면 push front한다는 것을 위에서 이야기 했습니다. 출발지부터 vertex \(v\)까지의 distance를 \(d_v\)이며, deque을 \(D\)라 하겠습니다.

 

Lemma 1. \(\max\{d_i\} - \min\{d_j\} \le 1\), \(i, j \in D\)

proof. 먼저, 현재 \(D\)가 Lemma 1을 만족한다고 가정해보자. 그리고 다른 vertex를 방문한다. 이제 이 vertex를 방문할 때 이용한 edge의 weight가 0이라면, 우리는 push front한다. 이때, \(\max\{d_i\}\)와 \(\min\{d_j\}\)의 값은 변하지 않는다. weight가 1이라면, push back 해준다. 이때, 우리는 두 가지 case를 생각할 수 있다. 첫 번째는 \(\max\{d_i\} - \min\{d_j\} =0\)인 경우이다. 이때 \(\max\{d_i\}\)는 1 증가하며, \(\min\{d_j\}\)는 \(|D|\) 따라 1 증가하거나 변하지 않는다. Lemma 1을 계속해서 만족한다. 두 번째 case는 \(\max\{d_i\} - \min\{d_j\} = 1\)인 경우이다. 이때 \(\max\{d_i\}\)는 변화하지 않으며, \(\min\{d_j\}\)는 경우에 따라 변할 수도 있고, 아닐 수 있다. 조금 더 자세하게, \(d_k = \min\{d_j\}\)인 \(k\)가 유일하다면 변하지 않는다. 그리고 어느 경우에도 Lemma 1. 은 계속 만족하는 상태이다. 초기 \(D\)에는 시작점 하나만 들어있으며, 이 distance는 0이다. 초기상태에서 Lemma 1.을 만족함으로, \(D\)는 항상 Lemma 1.을 만족한다.

 

Theorem. \(D\) is non-decreasing

 proof. Lemma 1.을 증명하는 과정에서, \(D\)가 non-decreasing이 아니게 되는 일은 일어나지 않는다는 것을 알 수 있다. 만약 \(D\)에서 현재 \(\max\{d_i\}\)보다 큰 \(d_k\)가 생겼다면, 이는 반드시 push back된다. 그리고 push back되기 전에  \(\max\{d_i\}=d_v\)였던 \(v \in D\)는 \(\min\{d_j\}=d_v\)가 된다. 따라서, \(D\)는 non-decreasing이다.

 

 Theorem을 통해 우리는 0-1 BFS에서의 deque이 non-decreasing인 것을 확인할 수 있습니다. 이러한 사실은 0-1 BFS가 Dijkstra's algorithm의 그리디를 그대로 이용하면서 deque을 이용할 수 있음을 말해줍니다.