SPFA 的最差测试用例

Question

最近，我阅读了有关最短路径更快算法的内容。我想知道如何构建一个测试用例，对于该测试用例，SPFA 的标准实现会非常非常慢。你知道吗？

通过标准实现，我的意思是来自维基百科的这个：

 procedure Shortest-Path-Faster-Algorithm(G, s)
1    for each vertex v ≠ s in V(G)
2        d(v) := ∞
3    d(s) := 0
4    offer s into Q
5    while Q is not empty
6        u := poll Q
7        for each edge (u, v) in E(G)
8            if d(u) + w(u, v) < d(v) then
9                d(v) := d(u) + w(u, v)
10                if v is not in Q then
11                    offer v into Q

Answer 1

例如。有N个顶点。第一个顶点是起点，第 N 个顶点是终点。对于第 i 个顶点，有 2 条边：(i, i+1, 1) 和 (1, i, 2*N) 其中 (a,b,c) 表示存在从 a 到 b 的边，权重为 c.

很容易看出这张图的最短路径是1->2->3->4->...->N。 假设对于 spfa 算法的第 7 行：对于 E(G) 中的每条边 (u, v)，具有较大 id 的顶点在具有较小 id 的顶点之前被访问。然后第 i 个顶点将被推入队列 max(1,i-1) 次。所以总的执行时间是 O(N^2)。

更进一步，如果对于第7行，id较大的顶点比id较小的顶点更晚被访问，则执行时间为O(N)。

对于spfa，总会存在时间复杂度最差的第7行的遍历顺序，也总是存在时间复杂度最好的第7行的遍历顺序。关键是信息如何通过最短路径传播。

Answer 2

根据 Ke Yang 的回答，具有 5 个顶点的图的最坏情况是：

在每次迭代中，队列将包含以下元素（队列的头部是最左边的元素）：

[1]
[5, 4, 3, 2]
[4, 3, 2]
[3, 2]
[2]
[5, 4, 3]
[4, 3]
[3]
[5, 4]
[4]
[5]

这显示了一个模式：4 + 3 + 2 + 1，这表明它的 O(N^2)。

但是仔细观察，每次轮询（出队）一个顶点时，它的所有出站边都会被考虑，第 7 行。因此第 8 行中的 if 被执行：

的总执行

顶点	违约次数	出境边缘	if
1	1	4	4
2	1	3	3
3	2	2	4
4	3	1	3
5	4	0	4

我们总共有： if 执行的次数：

即O(V^3)，其中V是顶点数。因为这个示例图会很密集，有 O(V^2) 条边。最终的复杂度可以写成 O(V*E)，其中 E 是边的数量。与 SPFA 最坏情况的复杂性相同。 https://en.wikipedia.org/wiki/Shortest_Path_Faster_Algorithm#Worst-case_performance

Answer 3

我尝试用实际代码测试之前的所有答案，除了 Luis 的答案外，其他答案似乎都不正确。 （SPFA 在 Ke 和 Vit 的回答上都花费了 $O(N)$ 时间）。

注意 Luis 的构造产生了一个密集图。为了完整起见，这是我提出的另一个测试用例，它涉及具有非负权重的 $O(N)$ 边，其中 SPFA 在 $\Theta(N^2)$ 时间内运行。施工如下：

1. 将源顶点设置为 $0$
2. 对于 $i\in [0,N/2)$，添加权重为 $N-i$ 的边 $i o N/2$
3. 对于$i\in [0,N/2-1)$，添加权重为0的边$i o i+1$
4. 对于$i\in [N/2+1, N)$，添加边$N/2 o i$，权重为0

顶点 $N/2$ 被推入队列 $\Theta(N)$ 次，每次我们将其从队列中弹出时，它都需要 $\Theta(N)$ 时间来遍历其邻接列表，从而产生所需的复杂性。

C++源码：

#include <cassert>
#include <climits>
#include <iostream>
#include <queue>
#include <vector>
using namespace std;

ostream &operator<<(ostream &os, pair<int, int> p) {
    os << "{" << p.first << ", " << p.second << "}";
    return os;
}
template <class T> ostream &operator<<(ostream &os, const vector<T> &v) {
    os << "{";
    for (size_t i = 0; i < size(v); ++i) {
        if (i) os << ", ";
        os << v[i];
    }
    os << "}";
    return os;
}

struct Edge {
    int u, v, w;
};

vector<int> spfa(int N, vector<Edge> edges) {
    vector<vector<pair<int, int>>> adj(N);
    for (auto [u, v, w] : edges) {
        assert(0 <= u && u < N);
        assert(0 <= v && v < N);
        adj[u].push_back({v, w});
    }
    cerr << "Input:\n";
    for (int i = 0; i < N; ++i) {
        cerr << "adj[" << i << "] = ";
        cerr << adj[i] << "\n";
    }
    cerr << "\n";
    vector<int> d(N, INT_MAX);
    d[0] = 0;
    queue<int> q;
    vector<bool> in_queue(N);
    int ops = 0;
    cerr << "Ops:\n";
    auto offer = [&](int v) {
        if (in_queue.at(v)) return;
        cerr << "offer "
             << "v = " << v << " "
             << "d[v] = " << d[v] << "\n";
        // cerr << "offer " << v << " " << d << "\n";
        in_queue.at(v) = true;
        q.push(v);
    };
    auto poll = [&]() {
        int u = q.front();
        q.pop();
        assert(in_queue.at(u));
        in_queue.at(u) = false;
        return u;
    };
    offer(0);
    while (!q.empty()) {
        int u = poll();
        cerr << "poll "
             << "u = " << u << " "
             << "d[u] = " << d[u] << "\n";
        // cerr << "poll " << u << " " << d << "\n";
        for (auto [v, w] : adj[u]) {
            ++ops;
            int new_d = d[u] + w;
            if (new_d < d[v]) d[v] = new_d, offer(v);
        }
    }
    cerr << "ops = " << ops << "\n";
    return d;
}

// Ke Yang's case (0-indexed)
// ops ~ 3*N
vector<Edge> gen_ke(int N) {
    vector<Edge> edges;
    for (int i = N - 1; i > 0; --i) edges.push_back({0, i, 2 * N});
    for (int i = 0; i < N - 1; ++i) edges.push_back({i, i + 1, 1});
    return edges;
}

// ops ~ 3*N
vector<Edge> gen_vit(int N) {
    vector<Edge> edges;
    for (int i = N - 1; i > 0; --i) edges.push_back({0, i, 3 * N - 2 * i});
    for (int i = 0; i < N - 1; ++i) edges.push_back({i, i + 1, 1});
    return edges;
}

// O(N^2) edges, ops ~ N^3 / 6
vector<Edge> gen_luis(int N) {
    vector<Edge> edges;
    for (int i = 0; i < N; ++i)
        for (int j = i + 2; j < N; ++j) edges.push_back({i, j, 2 * (N - i)});
    for (int i = 0; i + 1 < N; ++i) edges.push_back({i, i + 1, 1});
    return edges;
}

// O(N) edges, ops ~ N^2/4
vector<Edge> gen_good(int N) {
    vector<Edge> edges;
    for (int i = 0; i < N / 2; ++i) edges.push_back({i, N / 2, N - i});
    for (int i = N / 2 + 1; i < N; ++i) edges.push_back({N / 2, i, 0});
    for (int i = 0; i < N / 2 - 1; ++i) edges.push_back({i, i + 1, 0});
    return edges;
}

int main() {
    int N = 100;
    // auto edges = gen_ke(N);
    // auto edges = gen_vit(N);
    // auto edges = gen_luis(N);
    auto edges = gen_good(N);
    vector<int> dists = spfa(N, edges);
    cout << dists << "\n";
}

Ke Yang 在 $N=10$ 上的测试用例的输出：

Input:
adj[0] = {{9, 20}, {8, 20}, {7, 20}, {6, 20}, {5, 20}, {4, 20}, {3, 20}, {2, 20}, {1, 20}, {1, 1}}
adj[1] = {{2, 1}}
adj[2] = {{3, 1}}
adj[3] = {{4, 1}}
adj[4] = {{5, 1}}
adj[5] = {{6, 1}}
adj[6] = {{7, 1}}
adj[7] = {{8, 1}}
adj[8] = {{9, 1}}
adj[9] = {}

Ops:
offer v = 0 d[v] = 0
poll u = 0 d[u] = 0
offer v = 9 d[v] = 20
offer v = 8 d[v] = 20
offer v = 7 d[v] = 20
offer v = 6 d[v] = 20
offer v = 5 d[v] = 20
offer v = 4 d[v] = 20
offer v = 3 d[v] = 20
offer v = 2 d[v] = 20
offer v = 1 d[v] = 20
poll u = 9 d[u] = 20
poll u = 8 d[u] = 20
poll u = 7 d[u] = 20
poll u = 6 d[u] = 20
poll u = 5 d[u] = 20
poll u = 4 d[u] = 20
poll u = 3 d[u] = 20
poll u = 2 d[u] = 20
poll u = 1 d[u] = 1
offer v = 2 d[v] = 2
poll u = 2 d[u] = 2
offer v = 3 d[v] = 3
poll u = 3 d[u] = 3
offer v = 4 d[v] = 4
poll u = 4 d[u] = 4
offer v = 5 d[v] = 5
poll u = 5 d[u] = 5
offer v = 6 d[v] = 6
poll u = 6 d[u] = 6
offer v = 7 d[v] = 7
poll u = 7 d[u] = 7
offer v = 8 d[v] = 8
poll u = 8 d[u] = 8
offer v = 9 d[v] = 9
poll u = 9 d[u] = 9
ops = 25

Answer 4

Ke Yang 的测试很容易被边的随机洗牌破坏。

小的修改打破了这个技巧：边缘必须是 (i, i+1, 1) 和 (1, i, N*3-i*2)。