Shortest path with negative edges

출처는 http://www.cs.tau.ac.il/~zwick/grad-algo-09/short-path.pdf

흔히 알려진 알고리즘은 벨만 포드를 사용한 $O(nm)$ 시간 알고리즘이다. 이 글에서는 $O((n + m)\sqrt n \log W)$ 알고리즘을 소개한다.

그래프에 음수 사이클이 없다면 퍼텐셜 함수가 존재해서 $p(u) - p(v) + w(u, v) \geq 0$ 이 되게 만들어 줄 수 있음이 잘 알려져 있다. 그래서 결정 문제를

• 음수 사이클을 찾거나
• 퍼텐셜 함수를 찾거나

로 정의할 수 있다. 퍼텐셜 함수를 찾을 수 있으면 거기서부터는 $O(m + n \log n)$ 에 최단 경로를 찾는 것이 쉽기 때문이다.

만약 모든 간선의 가중치가 -1 이상 (즉 음수 간선은 무조건 가중치 -1) 일 때 문제를 해결할 수 있다고 하자. 전체 문제는 이 제약된 문제를 $\log W$ 번 호출해서 해결할 수 있다.

대충 이런 식이다. 알고리즘은 재귀적이다 (proof by induction on $\min W \geq -2^K$)
각 간선의 가중치를 $w(e) = \lceil w(e) / 2 \rceil$로 조정한 후 위 결정 문제를 해결한다.
만약 저 가중치 반 그래프에서 음수 사이클이 나왔다면, 홀수 간선일때 편의를 봐준 rounding이기 때문에, 원래 그래프에서도 그 음수 사이클이 보존된다.

고로 가중치 반 그래프에서 음수 사이클이 안 나왔을 때가 흥미로운 경우이다. 이 경우에는 퍼텐셜이 나오는데, 퍼텐셜 함수를 두 배 해서 적용해 보면 $p(u) - p(v) + w(u, v) \geq -1$이 됨을 확인할 수 있고 위 제약된 문제를 풀면 된다.

이제 모든 간선의 가중치가 -1 이상일 때 문제를 해결하자. 간선 가중치가 $\{-1, 0\}$ 인 간선들만 가지고 따로 그래프를 만들고 SCC를 구한다. 만약 -1 가중치의 간선의 양 끝점이 같은 SCC에 속하면 무조건 음수 사이클이 존재한다. 이 경우에는 이를 찾아서 반환하고, 이런 게 없는 경우는 한 SCC에 있는 간선들은 모두 0의 가중치를 가진다.

dummy source를 만들고, source에서 모든 정점으로 가중치 0의 간선을 이어준 후 $\{-1, 0\}$ 인 간선만 가지고 최단 경로를 찾자. SCC를 묶었기 때문에 이는 DP로 $O(n + m)$ 에 구할 수 있다. 이 때 각 정점의 최단 경로의 값은 $0, -1, -2, ..., -R$ 의 꼴을 띈다. $L_i = \{v|dist(s, v) = -i\}$ 로 정의하자.

몇가지 관찰할 것은

• -1 인 간선들은 레벨이 증가하는 방향으로 이어짐
• 0인 간선들은 레벨이 같거나 증가하는 방향으로 이어짐
• 1 이상인 간선들은 조건 없음

이라는 것이다. 뭐 어쨌든 이 그래프에는 음수 사이클이 있을 수 있고, 아직 퍼텐셜을 찾을 수는 없다.

어떠한 정점이 negative하다는 것을 이 정점으로 들어오는 -1 간선이 있다는 것으로 정의하자. negative한 정점 하나를 골라서, 이 정점에서 도달 가능한 모든 정점의 퍼텐셜을 1만큼 줄여주는 연산을 생각한다. 퍼텐셜 함수는 $p(u) - p(v) + w(u, v)$ 의 형태이다. 이 연산이 새로운 -1 간선을 만들려면 p(v)가 그대로고 p(u) 만 감소해야 하는데 도달 가능한 정점을 모두 늘려서 그게 불가능하다. 고로 위 연산은 negative한 정점을 정확히 하나만 딱 지워주기 때문에, 이 연산을 n번 반복하면 문제가 무조건 해결된다. 단지 복잡도가 $O(nm)$ 인 것이 문제일 뿐이다.

현재 negative한 정점의 개수가 $k \geq 1$ 개라고 하자. 만약 $R \leq \sqrt k$ 라면, $\sqrt k$ 이상의 크기를 가지는 집합 $L_i$ ($i > 0$) 이 무조건 존재한다. 일단 그러한 집합 $L_i$ 가 존재한다면 $L_i$ 에 있는 원소들을 모두 negative하지 않게 만들어 줄 수 있다. 방법은 $L_i, L_{i + 1}, \ldots, L_{R}$ 에 대해서 퍼텐셜을 -1 씩 감소시키면된다. 왜냐면 1 이상인 간선들은 1만큼 줄여도 상관 없고, 0인 간선들은 레벨이 같거나 증가하는 방향으로 이어졌으니 dest가 그대로고 source가 증가할 수 없음, -1인 간선 역시 동일.

이 연산을 여러 번 반복할 수는 없으나, 어차피 단 한번만 하고, 그 다음부터는 다시 처음부터 할 거다. 또한 이 연산은 SCC랑 상관 없다. 그냥 원래 정점 기준으로 모두 하는 것이다.

이제 $R > \sqrt k$ 인 케이스를 보자. 다시 SCC로 돌아간다. DAG 상에서의 shortest path는 길이 -R 을 가진다. DAG상 길이 R의 path를 구한 후, 이제 원래 그래프에서 각 SCC에서 가장 처음 방문한 정점들을 $w_1, w_2, \ldots, w_R$ 이라고 하자. 구체적으로, DAG 상에서 길이 R의 path는 원래 그래프에서 R 이상의 길이를 가진다. 한 SCC에서 시간을 쓰기 때문이다. 각 SCC를 방문할 때 처음 방문한 정점은 negative하다. 그 정점들을 기록해 놓는 것이다.

원래 그래프로 돌아온다. 잠시 -1 가중치 간선들을 모두 0으로 바꿔두자. dummy source를 만들고, $w_i$ 에 속하지 않는 정점에 R의 가중치 간선, $w_i$ 에 속하는 정점에 $R - i$의 가중치 간선을 더한다. 이 그래프에서 최단 경로를 구하면, 최단 거리가 모든 정점에 대해 R 이하이다. 음수 가중치가 없으니 $O(n + m)$ 에 최단 경로를 구할 수 있다 (pq 대신 버킷 사용)

이렇게 구한 최단 경로 값을 퍼텐셜로 사용하면, 이제 $w_i$ 들이 모두 nonnegative해지거나, 아니면 음수 사이클을 찾음을 증명한다.

일단 새로운 -1 간선이 생기지 않음을 관찰하자.

• $w(u, v) \geq 0$ 이었다면, 퍼텐셜을 구할 때도 간선 가중치가 바뀌지 않는다. $p(v) \leq p(u) + w(u, v)$ 이니 여전히 nonnegative하다.
• $w(u, v) = -1$ 이었다면, $p(v) \leq p(u) + 0$ 이니 $p(v) - p(u) + w(u, v) \geq -1$ 이고, 가중치가 -1 이거나 그 이상이다.

그래서 손해 보는 건 없고, $w_i$ 들이 nonnegative해지는지만 보면 된다.

$w(u, w_i) = -1$ 이라고 하자. $p(u) > p(w_i)$ 인 경우는 위와 같은 이유로 상관이 없고 $p(u) = p(w_i)$ 인 경우만 보면 된다. $p(u) = p(w_i) \le R - i$ 이다. 초기 더미 노드에서 u로 가는 최단 경로는, 첫 간선으로 $w_j (j \geq i)$ 를 택할 수 밖에 없다. 구체적인 식은 $R - j + (w_j$ 에서 $u$로 가는 경로) $\le R - i$ 이다.

고로

• 새 그래프에서 ($w_j$ 에서 $u$로 가는 경로) $\le j - i$인 것이 존재한다. 원래 그래프의 가중치가 낮지 않으니 원래 그래프에서도 경로 가중치는 $j - i$ 이하이다.
• 당연하게도 $w_i$ 에서 $w_j$ 로 가는 경로의 가중치는 $i - j$ 이하이다.
• $u \rightarrow w_i$ 로 가는 간선 가중치가 -1 이다.

합하면 -1 이하이고, 고로 음수 사이클을 찾을 수 있다.

음수 사이클을 못 찾았다면 저런 경우는 존재하지 않는다. 고로 모든 $w_i$ 들이 nonnegative해졌다.

매번 negative vertex가 $\sqrt k$ 개씩 감소한다. $k \leq 1/4n^2$ 면 $k - \sqrt k \leq 1/4(n-1)^2$ 이기 때문에 이를 $O(\sqrt n)$ 번 반복하면 퍼텐셜을 얻거나 사이클을 찾을 수 있다. 매 감소 연산은 $O(n+m)$ 시간을 사용한다. 본인의 구현은 $n, m = 20000$ 정도에서 Bellman Ford보다 3.5배 정도 빨랐는데, 데이터가 얼마나 강한지는 모르겠다. (Bellman-Ford 구현, Scaling 구현)

현재 SOTA인 BCF23 와 비교해 보면 꽤 큰 차이점이 있다. BCF23도 scaling이 있는데, 각 scaling에서 푸는 restricted graph라고 부르는 그래프는 여기서 보는 그래프보다 더 강력한 조건을 요구한다. BCF23의 핵심 아이디어는 restricted graph에 어떠한 신기한 separator structure가 있고 이를 통해 분할 정복을 할 수 있다는 건데, 이 알고리즘은 굉장히 plain한 augmenting path 류로 보인다 (초기 부족한 해에서 시작해서 고치거나 모순 찾거나). Separator를 찾으려면 $O(\log N)$ 번 샘플링을 해야 하는데, 실제 구현에서는 정확한 답을 얻기 위해 필요한 constant factor가 크다고 생각이 든다. randomized algorithm로 practice에서 이론적으로 보장된 성능을 뽑기가 다소 어렵다는 인식이 있는데, 일단 subproblem들이 whp로 exact해야 한다는 가정이 많이 필요하기도 하고, 흔히 쓰는 Chernoff bound 같은건 $N$ 이 충분히 커야지만 theoretical bound가 나오는데 현실에서는 $N$ 이 작은 인스턴스가 많다는 것 등이 문제가 되는 것 같다.