给定 n 顶点上的加权有向无环图，使得每个顶点的入度最多为 5 ，出度最多为 5 。节点 0, 1, ..., n - 1 的方向是这样的0 1 2 3 45 6 7 8 910 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) ，而 k 的最佳选择是 k=n^(2/3) ，它给出了 O(n^(4/3)) 和总查询 O(q) 预处理的总复杂度
关于algorithm - 小度有向无环图中的最短路径，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/43653253/