有向无环图中的最短路径问题和小度数相关。

Question

给定一个有向无环图，其中每个顶点的入度和出度都不超过5个，共有n个顶点。节点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)的动态规划更好地解决这个问题（显然在此处不起作用）？

- Artur

---

请更具体地说明图形布局。每一行是否由恰好5个节点组成，这意味着“n”是5的倍数？ - Codor

是的，每一行都由5个节点组成，除了最后一行可能包含剩余的<= 5个节点。 - Artur

为什么使用动态规划时，时间复杂度是O(n^2)？我认为它是O(e)，其中e是图的边数。例如，每个节点最多可以有5条边，复杂度将为O(5n) = O(n)。 - Santiago Gil

每个查询的时间复杂度为O(n)，因此实际上是O(nq)。抱歉。 - Artur

如果图是有向的，并且边只能从一行到下一行而不是上一行。那么你只需要确定两个节点是否相连吗？然后距离将是 floor(v/5) - floor(u/5)。 - user1470500

Answer 1

这似乎太好了，如果不是的话很抱歉...您可以获得O(n)（编辑：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=n^(2/3)，这将给出预处理的总复杂度为O(n^(4/3))和总查询为O(q)。

- gdelab

---

也许你可以通过递归应用这种方法来进一步改进。 - gdelab

要在O(n^2)的时间内计算所有最短距离：只需按照通常的顺序遍历整个图。对于每个节点，存储从之前每个节点到该节点的距离。当您到达一个新节点x时，对于它之前的每个节点，只需比较由x的5个可能的前任给出的5种可能性。这对于每个x是O(n)，总共是O(n^2)。 - gdelab

这是一个不错的解决方案 - 为了确保实际复杂度没有混淆，也许你应该将其写成 O(n ^ (4/3)) 而不是 O(n^4/3)。 - danbanica