Sait2000's profile image

Sait2000

July 17, 2022 00:00

다익스트라에 제출한 SPFA 저격 데이터

다익스트라 알고리즘은 모든 간선이 음이 아닌 가중치를 가질 때 사용할 수 있는 최단거리 알고리즘으로, 새로 확인할 정점을 고를 때 매번 모든 정점의 알려진 최단거리를 비교하는 방식으로는 $O(V^2)$에, 우선순위 큐를 사용하면 $O(E \log E)$에 구현할 수 있습니다. 한편 벨만-포드 알고리즘의 변형이라고 볼 수 있는 SPFA 알고리즘은 간선의 가중치가 음수인 경우에도 사용할 수 있으며, 최악의 경우의 시간복잡도는 $O(VE)$이지만, $O(E \log E)$ 다익스트라 알고리즘이 정해인 문제에서도 저격 데이터가 없는 경우 통과하는 경우도 있습니다.

이 글에서는 SPFA 알고리즘의 기본적인 구현 및 SLF, LLL 등의 최적화와, 다익스트라 문제에서 SPFA 알고리즘에 대한 저격 데이터를 소개합니다.

문제

이 글에서 다루는 문제 명세는 이 글에서와 같습니다.

SPFA 기본형

SPFA의 코드는 BFS나 $O(E \log E)$ 다익스트라와 비슷합니다. 다만 다익스트라와 다르게 우선순위 큐 대신 BFS처럼 큐를 사용하고, 대신 BFS와 다르게 어떤 정점의 최단거리가 한 번이 아니라 여러 번 갱신될 수 있기 때문에, 큐에 정점을 넣을 때 이미 큐에 있는 정점은 넣지 않습니다.

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
const ll INF = 1LL << 60;

vector<ll> shortest_SPFA(
    const vector<vector<pair<int, int>>>& graph,
    int start
) {
    int n = graph.size();
    vector<ll> dist(n, INF);
    deque<int> q;
    vector<int> in_queue(n, 0);
    auto push = [&](int v, ll d) {
        if (d < dist[v]) {
            dist[v] = d;
            if (in_queue[v] == 0) {
                in_queue[v] = 1;
                q.push_back(v);
            }
        }
    };
    auto pop = [&]() {
        int v = q.front();
        in_queue[v] = 0;
        q.pop_front();
        return v;
    };
    push(start, 0);
    while (!q.empty()) {
        int v = pop();
        ll d = dist[v];
        for (auto [u, w] : graph[v]) {
            push(u, d + w);
        }
    }
    for (ll& d : dist) {
        if (d >= INF) {
            d = -1;
        }
    }
    return dist;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int V, E;
    cin >> V >> E;
    vector<vector<pair<int, int>>> graph(V);
    for (int i = 0; i < E; ++i) {
        int u, v, w;
        cin >> u >> v >> w;
        u--, v--;
        graph[u].push_back({v, w});
    }
    auto dist = shortest_SPFA(graph, 1 - 1);
    cout << dist[V - 1] << '\n';
}

SPFA에서 한 정점이 큐에 들어갈 때마다 BFS tree(?) 상의 거리, 즉 해당 정점의 알려진 최단 경로에 포함된 간선의 수의 하한이 증가하므로, 그래프에 음수 사이클이 없다는 가정 하에 한 정점은 최대 $V - 1$번 큐에 들어갑니다. 따라서 각 간선 또한 $O(V)$번 확인되어서 총 시간복잡도가 $O(VE)$가 됩니다.

따라서 SPFA 알고리즘을 저격하려면 큐에 여러 번 들어가는 정점이 있어서 이 정점에 많은 간선이 연결되어 있어야 합니다.

한 정점이 여러 번 큐에 들어가게 하기 위해서는 사용하는 간선의 개수가 많아질수록 경로의 총 거리가 짧아지는 형태의 그래프가 필요합니다.

아래는 데이터를 생성하는 코드입니다.

#include <bits/stdc++.h>
using namespace std;

const int MAXV = 100000;
const int MAXE = 500000;
const int MAXW = 1000000;

struct {
    int u, v, w;
} edges[MAXE];

int main() {
    int n = 1;
    int ne = 0;
    auto f = [&](int u, int v, int w) {
        edges[ne++] = {u, v, w};
    };
    for ( ; n + 2 <= MAXV; ) {
        n += 2;
        f(n - 2, n, 3);
        f(n - 2, n - 1, 1);
        f(n - 1, n, 1);
    }
    for (int i = n - 1; ; --i) {
        for (int j = 1; j + i <= n; ++j) {
            if (ne >= MAXE) break;
            f(i + j, j, MAXW);
        }
        if (ne >= MAXE) break;
    }

    printf("%d %d\n", n, ne);
    for (int i = 0; i < ne; ++i) {
        printf("%d %d %d\n", edges[i].u, edges[i].v, edges[i].w);
    }

    return 0;
}

만약 SPFA 알고리즘에서 간선 방문 순서를 주어지는 순서의 역순으로 하거나 간선을 가중치가 작은 것부터 방문하는 등 간선을 방문하는 순서에 따라 저격이 안 될 수도 있는데, 이를 막기 위해서 간선이 갈라질 때 처음 보이는 간선의 가중치가 작은 쪽이 더 간선 개수가 작도록 만드는 방법도 있습니다.

for ( ; n + 2 <= MAXV; ) {
    n += 2;
    f(n - 2, n, 3);
    f(n - 2, n - 1, 1);
    if (n + 2 <= MAXV && rand() % 37 % 2) {
        n += 2;
        f(n - 2, n - 1, 1);
        f(n - 1, n, 1);
        f(n - 3, n, 5);
    } else {
        f(n - 1, n, 1);
    }
}

SLF

SLF(Small Label First) 최적화는 새로 큐에 넣는 정점에 대해서 그 정점의 알려진 최단거리가 큐의 맨 앞의 정점의 알려진 최단거리보다 짧으면 그 정점을 큐의 맨 뒤가 아닌 맨 앞에 넣는 최적화입니다. 따라서 엄밀히 말하면 큐가 아니라 덱(deque)이 필요합니다. 최단거리가 짧은 경우를 더 일찍 확인하게 되어서 알고리즘이 더 빨리 종료할 수도 있습니다.

구현은 SPFA 코드에서 push 함수를 다음과 같이 바꾸면 됩니다.

auto push = [&](int v, ll d) {
    if (d < dist[v]) {
        dist[v] = d;
        if (in_queue[v] == 0) {
            in_queue[v] = 1;
            q.push_back(v);
            if (dist[q.front()] > dist[q.back()]) {
                q.pop_back();
                q.push_front(v);
            }
        }
    }
};

비슷하지만 조금 다른(틀린?) 구현으로 일단 큐 뒤에 정점을 넣은 다음 거리 조건이 만족할 때 맨 앞 정점과 맨 뒤 정점을 바꾸는 방법이 있습니다. 저는 swap SLF라 부릅니다. 이렇게 구현하면 덱 대신 큐로 구현할 수 있다는 미묘한 장점이 있습니다.

auto push = [&](int v, ll d) {
    if (d < dist[v]) {
        dist[v] = d;
        if (in_queue[v] == 0) {
            in_queue[v] = 1;
            q.push_back(v);
            if (dist[q.front()] > dist[q.back()]) {
                swap(q.front(), q.back());
            }
        }
    }
};

SLF를 저격하기 위해서는 원래 데이터처럼 갈림길을 만들면서 갈림길 간선들의 가중치를 2배로 키운 다음 각 정점에 더미로 가중치 1인 간선과 정점을 새로 달아주면 됩니다. 이렇게 하면 원래 있던 간선들을 방문할 때는 큐의 맨 앞에 더미 정점이 들어있거나 더미 정점보다도 최단거리가 짧은 정점이 들어있게 됩니다. (Swap SLF의 동작은 정확히 모르겠는데 이 데이터로 저격이 되긴 합니다)

for ( ; n + 6 <= MAXV; ) {
    n += 6;

    // dummy
    f(n - 6, n - 3, 1);
    f(n - 5, n - 2, 1);
    f(n - 4, n - 1, 1);

    f(n - 6, n, 8);
    f(n - 6, n - 5, 2);
    f(n - 5, n - 4, 2);
    f(n - 4, n, 2);
}

TODO: 위 데이터는 swap SLF에서 간선 순서를 무작위로 방문하거나 가중치가 작은 간선부터 방문하는 경우 저격이 안 됩니다.

한편 SLF에서 정점을 맨 앞에 넣는 기준을 역치 $k$를 정해서 맨 앞 정점의 거리에 비해 지금 넣을 정점의 거리가 $k$ 이상 짧을 때만 앞에 넣는 것으로 바꿀 수도 있습니다. 적당한 $k$ 값은 실험적으로 찾아야 하겠지만 $k = \infty$일 때가 기본 SPFA, $k = 0$일 때가 SLF, $k = -\infty$일 때가 방문체크 없는 dfs가 되므로 $k$의 절대값이 너무 커지면 잘 동작하지 않을 것으로 추측합니다.

auto push = [&](int v, ll d) {
    const ll k = -300;
    if (d < dist[v]) {
        dist[v] = d;
        if (in_queue[v] == 0) {
            in_queue[v] = 1;
            q.push_back(v);
            if (dist[q.front()] - k > dist[q.back()]) {
                q.pop_back();
                q.push_front(v);
            }
        }
    }
};

이런 경우는 원래 간선들의 가중치를 2배보다 더 많이 키워서 역치의 영향력이 작아지도록 하면 됩니다.

for ( ; n + 6 <= MAXV; ) {
    n += 6;

    // dummy
    f(n - 6, n - 3, 1);
    f(n - 5, n - 2, 1);
    f(n - 4, n - 1, 1);

    int w1 = 1000;
    int w2 = (w1 - 1) / 3;
    f(n - 6, n, w1);
    f(n - 6, n - 5, w2);
    f(n - 5, n - 4, w2);
    f(n - 4, n, w2);
}

LLL

LLL(Large Label Last)는 큐 뒤에 정점을 넣을 때마다 큐 맨 앞에 정점의 알려진 최단거리가 현재 큐에 있는 정점의 최단거리 평균보다 길면 그 정점을 앞에서 꺼내서 맨 뒤에 넣습니다. 이를 평균보다 최단거리가 짧거나 같은 정점이 맨 앞에 올 때까지 반복합니다.

vector<ll> shortest_SPFA_LLL(
    const vector<vector<pair<int, int>>>& graph,
    int start
) {
    int n = graph.size();
    vector<ll> dist(n, INF);
    deque<int> q;
    vector<int> in_queue(n, 0);
    ll sum_dist = 0;
    auto push = [&](int v, ll d) {
        if (d < dist[v]) {
            if (in_queue[v] == 1) {
                sum_dist -= dist[v];
                sum_dist += d;
            }
            dist[v] = d;
            if (in_queue[v] == 0) {
                in_queue[v] = 1;
                sum_dist += dist[v];
                q.push_back(v);
                ll avg = sum_dist / int(q.size());
                while (avg < dist[q.front()]) {
                    int u = q.front();
                    q.pop_front();
                    q.push_back(u);
                }
            }
        }
    };
    auto pop = [&]() {
        int v = q.front();
        in_queue[v] = 0;
        sum_dist -= dist[v];
        q.pop_front();
        return v;
    };
    push(start, 0);
    while (!q.empty()) {
        int v = pop();
        ll d = dist[v];
        for (auto [u, w] : graph[v]) {
            push(u, d + w);
        }
    }
    for (ll& d : dist) {
        if (d >= INF) {
            d = -1;
        }
    }
    return dist;
}

저격 데이터는 LLL 최적화가 잘 동작하는 것을 막기 위해서 SLF와 비슷하게 더미 정점을 추가하는데 이때 가중치를 1이 아니라 최대한 크게 설정해줍니다. 그러면 더미 정점의 최단거리가 원래 정점들에 비해 크므로 원래 정점의 최단거리가 평균보다 작게 되어서 LLL 최적화가 실행돼도 원래 정점이 큐의 맨 앞으로 오면 큐 회전이 멈추게 됩니다.

for ( ; n + 6 <= MAXV; ) {
    n += 6;

    // dummy
    f(n - 6, n - 3, MAXW);
    f(n - 5, n - 2, MAXW);
    f(n - 4, n - 1, MAXW);

    f(n - 6, n, 8);
    f(n - 6, n - 5, 2);
    f(n - 5, n - 4, 2);
    f(n - 4, n, 2);
}