定向非循环图中的最短路径具有小的程度
给定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) 。
然后，可以考虑仅包含两个块之间边界处的节点的缩减图，其中边的值等于它们之间刚刚计算的最短路径。此缩减图的大小为O(k) 。 在时间O(k^2)计算该图中的所有最短路径。
总预处理时间： O((n/k)^2 + k^2) 。 以k=sqrt(n) ，你得到O(n)预处理。
查询时间为O(1) ：取u块的末端5个节点，v块的起始5个（如果块不同），则只需比较u-> v的25个可能性
编辑
当然这是错误的。 你实际上有k块要计算最短路径，所以该步骤的总复杂度为O(k*(n/k)^2) 。 所以总和为O(n^2/k + k^2) ， O(n^2/k + k^2)的最佳选择是k=n^(2/3) ，这给出了O(n^(4/3))和总查询O(q)
上一篇: Shortest path in Directed Acyclic Graph with small degree