Even-Shiloach Algorithm

Even-Shiloach Algorithm은 Unweighted directed graph $G = (V, E)$ 에 대해서 incremental / decremental SSSP를 빠르게 해결하는 알고리즘이다. Naive하게는 매번 BFS를 해서 $O(m^2)$ 시간에 해결할 수 있는데, 이 알고리즘을 사용하면 이를 $O(nm)$ 으로 최적화할 수 있다. $O(m^2)$ 에 비해서 엄청나게 효율적이진 않지만 분명히 nontrivial한 bound이고, 내가 아는 state-of-the-art method는 전부 다 Near-linear가 아니라 $O(nm)$ 에 훨씬 가까운 바운드이다. 그것도 복잡한 알고리즘들이 대다수.

이 글에서는 원래 Even-Shiloach Algorithm보다 강한 statement를 증명한다 - 특정 상수 $k \le n$ 에 대해, 거리가 $k$ 이하인 점에 대한 Incremental / Decremental BFS Tree를 $O(km)$ 시간에 관리할 수 있다. $k = n$ 으로 두면 original statement가 된다. (BFS Tree를 알면 최단 경로도 알 수 있다.)

Incremental한 경우는 쉬운 편이다 (BOJ 8452). 간선 $(u \rightarrow v)$ 가 추가되었을 때 $dist[v] > dist[u] + 1$ 이면 $v$ 방향에서 가중치가 줄어드는 노드들에 대해서만 BFS를 하면 된다. 각 노드가 처리되었다는 것은 $dist$ 가 기존에 비해서 $1$ 이상 줄었다는 뜻이다. 가능한 $dist$ 의 후보는 최대 $k$ 개이니, 총 시간 복잡도는 $O(km)$ 이 된다.

Decremental한 경우는 조금 더 까다롭다. 먼저 초기 BFS를 통해서 BFS Tree를 구성하고, 각 노드 $v$ 에 대해서 $v$ 로 들어오는 (indegree) 간선들을 consistent한 order로 정렬해 놓는다. (약간 원형 큐 같은 느낌으로 사용할 것이다.) 우리가 관리할 BFS Tree는 루트가 아닌 모든 노드에 대해 다음과 같은 invariant를 유지한다: 해당 노드의 모든 가능한 조상 중, 위 order에서 최소인 조상을 부모로 가진다.

간선 $(u \rightarrow v)$ 가 제거되었다고 하자. 만약 $u \rightarrow v$ 가 BFS 트리를 이루지 않는다면 그냥 리스트에서 naive하게 제거해 준다. Linked list 사용시 $O(1)$ 이니 자명한 케이스이다. 아니라면, 이 제거 쿼리에 영향을 받는 것은 $v$ 의 서브트리 영역이 될 것이다. 정확히는, $v$ 의 서브트리에서 어떠한 connected area에 대해서 최단 경로가 바뀌고, 그 영역의 BFS tree는 완전히 뒤죽박죽이 될 것이다. 한편으로, 어떠한 노드 $w$ 가 $v$ 의 서브트리에 있고 간선 제거 후에도 여전히 최단 경로 길이가 그대로라면, $w$ 의 서브트리는 건드릴 필요가 없다. 목표는, Dijkstra's algorithm을 정말 careful하게 적용해서

• 각 노드들을 최단 거리가 증가하는 순서대로 처리하고
• 변화가 있는 노드들만 방문하게끔

하는 것이다.

먼저 $v$ 를 처리하자. (이 때 거리를 $d$ 라고 하자.) 간선을 지우기 전의 거리를 유지하면서 새로운 부모를 찾을 수 있는지 확인한다. 위에서 관리한 invariant에 의해, 지워진 간선보다 order가 뒤에 있는 간선들만 찾으면 되고, order 순서대로 스캔하면서 거리가 맞으면 바로 매칭해 주면 된다. 그러한 부모를 찾았으면 그냥 거기서 끝내면 된다.

못 찾았다면, 거리를 늘려야 한다. 이는 자신의 거리도 틀렸고, 자신의 자식들의 거리도 틀렸다는 (안 틀렸을 수도 있지만, 최소한 부모를 바꿔야 하는) 상황이라는 것이다. 일단 자신의 부모를 삭제하고, 자신의 거리를 $1$ 씩 늘려주고, 모든 트리 상의 자식 $w$ 를 보면서, 만약 이 노드가 아직 처리되지 않은 노드라면 큐에 넣어준다. (여기서 부모를 굳이 삭제해 주는 이유는 다음 스캔에서 order를 맨 앞에서부터 보고 싶기 때문이다. 거리가 증가했으니 invariant를 믿을 수 없고 당연히 처음부터 스캔을 돌려야 한다.)

이제 다음에 큐에서 보는 노드들은 모두 루트와의 거리가 "최소" $d + 1$ 인 노드들이다. 이 거리를 실제로 유지할 수 있으면, 거기서 끝내면 된다. 만약에 유지할 수 없다면, 이 노드의 거리는 최소 $d+2$ 가 되며, 인접한 노드들에 대해서도 거리가 최소 $d+2$ 가 될 것이다. 이러한 식으로 큐가 빌 때까지 반복하면 된다. 여담으로 현재 큐에서 처리되고 있는 노드는 거리 함수를 증가시켰기 때문에 절대 부모가 될 수 없고, 큐에서 처리가 종료된 이후에만 부모로 관리할 수 있음에 유의하자. 또한, 부모가 지워진 정점들에 대해서는, order의 처음부터 스캔을 해야 한다는 차이가 있다.

거리가 늘어나는 과정에서 알고리즘이 실질적으로 사용하는 연산은 총 세 종류이다:

• 큐에서 원소를 뽑는 과정
• 포인터를 돌리면서 부모를 바꾸거나 거리를 늘리는 과정
• 인접한 노드들을 처리하는 과정

각 과정의 분석은 다음과 같다:

• 큐에 원소가 추가되었다는 것은 해당 노드의 부모 혹은 거리가 무조건 바뀐다는 뜻이기 때문에 (2) 의 연산을 무조건 함의하고, 고로 (2) 의 연산량 이하이다.
• 거리가 $k$ 이하인 시점까지 돌릴 수 있는 포인터의 수가 $k \times deg(v)$ 이기 때문에 합하면 $km$ 이다.
• 인접한 노드를 모두 확인할 때는 거리가 순증가했기 때문에 역시 합하면 $km$ 이다.

아래에는 위와 같은 방법으로 BOJ 8452를 온라인으로 해결하(려고 했으나 TLE를 받은 ㅋㅋ)는 코드이다. 내 구현은 원래 상수가 조금 큰 편이라 적당히 다듬으면 같은 코드로 AC를 받을 수 있다고 생각한다.

https://gist.github.com/koosaga/48d37df4b77f02c6f878d5e330e75770