小度有向无环图中的最短路径
Shortest path in Directed Acyclic Graph with small degree
给定 n 个顶点的加权有向无环图，每个顶点的入度至多 5 和出度至多 5。节点 0, 1, ..., n - 1 的方向如下
0 1 2 3 4
5 6 7 8 9
10 11 12 13 14
...
n-5 n-4 n-3 n-2 n-1
边只能从一行中的一个节点到下一行中的某个节点。
我们将得到 q 个查询，询问从 u 到 v 的最短路径长度。这里 n 可以达到 10^5，q 可以达到 10^4。权重都是正整数。
我们能否比 O(nq) 动态规划（显然在这里行不通）做得更好？
这似乎好得令人难以置信，抱歉，如果不是...你可以得到 O(n) (EDIT: O(n^(4/3))) 预处理和 O (1)查询.
我认为您知道如何及时计算图中所有节点之间的所有最短距离 O(n^2)。 （确实有可能，你好像也知道）
将图表分成 k 个块，每个块包含 n/(5*k) 行。 （块应该在完整的行上开始和结束，并且两个连续的块在各自的第一行和最后一行重叠）
计算每个块中所有节点（尤其是第一行和最后一行）之间的最短路径：O((n/k)^2).
那么你可以考虑只包含两个块之间边界处的节点的缩减图，边值等于它们之间的最短路径，你刚刚 computed.This 缩减图的大小为 O(k)。
及时计算该图中的所有最短路径 O(k^2)。
总预处理时间：O((n/k)^2 + k^2)。采取 k=sqrt(n)，你得到 O(n) 预处理。
那么查询时间为O(1)：取u的block末尾的5个节点，v的block开始的5节点（如果block不同），只需要比较25 u->v
的可能性
编辑
当然是假的。您实际上有 k 个块来计算最短路径，因此该步骤的总复杂度为 O(k*(n/k)^2)。所以总数是 O(n^2/k + k^2)，k 的最佳选择是 k=n^(2/3)，这给出了预处理的总复杂度 O(n^(4/3)) 和总查询 O(q)
给定 n 个顶点的加权有向无环图，每个顶点的入度至多 5 和出度至多 5。节点 0, 1, ..., n - 1 的方向如下
0 1 2 3 4
5 6 7 8 9
10 11 12 13 14
...
n-5 n-4 n-3 n-2 n-1
边只能从一行中的一个节点到下一行中的某个节点。
我们将得到 q 个查询，询问从 u 到 v 的最短路径长度。这里 n 可以达到 10^5，q 可以达到 10^4。权重都是正整数。
我们能否比 O(nq) 动态规划（显然在这里行不通）做得更好？
这似乎好得令人难以置信，抱歉，如果不是...你可以得到 O(n) (EDIT: O(n^(4/3))) 预处理和 O (1)查询.
我认为您知道如何及时计算图中所有节点之间的所有最短距离 O(n^2)。 （确实有可能，你好像也知道）
将图表分成 k 个块，每个块包含 n/(5*k) 行。 （块应该在完整的行上开始和结束，并且两个连续的块在各自的第一行和最后一行重叠）
计算每个块中所有节点（尤其是第一行和最后一行）之间的最短路径：O((n/k)^2).
那么你可以考虑只包含两个块之间边界处的节点的缩减图，边值等于它们之间的最短路径，你刚刚 computed.This 缩减图的大小为 O(k)。
及时计算该图中的所有最短路径 O(k^2)。
总预处理时间：O((n/k)^2 + k^2)。采取 k=sqrt(n)，你得到 O(n) 预处理。
那么查询时间为O(1)：取u的block末尾的5个节点，v的block开始的5节点（如果block不同），只需要比较25 u->v
编辑
当然是假的。您实际上有 k 个块来计算最短路径，因此该步骤的总复杂度为 O(k*(n/k)^2)。所以总数是 O(n^2/k + k^2)，k 的最佳选择是 k=n^(2/3)，这给出了预处理的总复杂度 O(n^(4/3)) 和总查询 O(q)