SOFA 的最差测试用例
Worst test case for SPFA
最近看了最短路径加速算法。我想知道如何构建一个测试用例，对于该测试用例，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
例如。有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行的遍历顺序。关键是信息如何通过最短路径传播。
根据 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 被执行：
Vertex
Times dequed
Outbound edges
total execution of 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
最近看了最短路径加速算法。我想知道如何构建一个测试用例，对于该测试用例，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
例如。有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行的遍历顺序。关键是信息如何通过最短路径传播。
根据 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 被执行：
| Vertex | Times dequed | Outbound edges | total execution of 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