给定一个带有自环的有向加权图，找出距离给定节点x恰好为k个单位距离的节点列表是什么？

Question

每条边的权重为1，图中可能存在环。如果一个节点有自环，那么它到自身的距离可以是0到无穷远的任何值，这取决于我们经过自环的次数。

我已经使用广度优先搜索算法解决了这个问题，但是由于距离的限制达到10^9级别，因此BFS速度较慢。

我们将在给定图形上进行多个查询，形式为（距离，源），输出是从源顶点开始恰好处于给定距离的节点列表。

约束条件：

1<=Nodes<=500
1<queries<=500
1<=distance<=10^9

我有一种感觉，如果节点数较少，将会有许多重复的计算，但我无法想象如何将问题减小到更小的问题。

有什么有效的方法可以解决这个问题吗？

编辑：我尝试过使用矩阵求幂，但对于给定的限制来说速度太慢了。这个问题有一个时间限制为1秒。

- A. Sam

Answer 1

假设你有一张图 G = (V,E)，那么我们可以用下面的方式定义邻接矩阵 A：

A[i][j] = 1       (V[i],V[j]) is in E
          0       otherwise

在这个矩阵中，对于每个 k：

(A^k)[i][j] > 0 if and only if there is a path from v[i] to v[j] of length exactly k.

这意味着通过创建矩阵并计算指数，您可以轻松地获得答案。

为了快速计算指数，您可以使用指数平方法，它将产生O(M(n)^log(k))，其中M(n)是nXn矩阵的矩阵乘法成本。

这也可以在查找同一图上的不同查询时节省一些计算量。

附录 - 声明证明:

基: A^1 = A，并且确实在A中，A[i][j]=1当且仅当(V[i]，V[j])在E中

假设：假设对于所有l

A^k = A^(k-1)*A。从归纳假设，A^(k-1)[i][j] > 0 当且仅当从V[i]到V[j]的长度为k-1的路径存在。

让我们检查具有索引i和j的两个顶点v1,v2。 如果它们之间存在长度为k的路径，则为v1->...->u->v2。让u的索引为m。 从归纳假设可知，因为有一条路径，A^(k-1)[i][m] > 0。此外，A[m][j] = 1，因为(u,v2) = (V[m],V[j])是一条边。

A^k[i][j] = A^(k-1)*A[i][j] = A^(k-1)[i][1]A[1][j] + ... + A^(k-1)[i][m]A[m][j] + ... + A^(k-1)[i][n]A[n][j] 

由于 A[m][j] > 0 且 A^(k-1)[i][m] > 0，因此 A^(k-1)*A[i][j] > 0

如果不存在这样的路径，则对于每个顶点 u，使得（u,v2）是一条边，则从 v 到 u 的长度为 k-1 的路径不存在（否则 v1->..->u->v2 是长度为 k 的路径）。

然后，使用归纳假设，我们知道如果 A^(k-1)[i][m] > 0，则对于所有 m，A[m][j] = 0。
如果我们将其分配在定义 A^k[i][j] 的总和中，我们得到 A^k[i][j] = 0

证毕

小提示：技术上，A^k[i][j] 是长度恰好为 k 的路径数。这可以类似地证明，但需要更多的细节注意。
为了避免数字增长过快（这会增加 M(n)，因为您可能需要大整数来存储该值），并且由于您只关心除 0/1 外的值 - 您可以将矩阵视为布尔值 - 仅使用 0/1 值并修剪任何其他内容。

- amit

---

对于小的k和大的n，朴素的BFS方法会更便宜。否则，这是可行的方法。 - G. Bach

虽然你的方法是正确的，但对于500x500矩阵进行10^9次查询来说太慢了。原问题的时间限制为1秒。 - A. Sam

我用你的方法解决了它 + 布尔矩阵快速乘法。 - A. Sam

Answer 2

如果你的图中有循环，那么你可以推断出每个相邻节点之间存在一个链接，其距离为cycle * N + 1，因为你可以无限迭代。

这让我想到了一个点子，我们可以利用这些循环来优化算法！在检测到循环时，使用BFS计算offset + cycle*N，然后我们就可以更接近目标(K)了。

这样就可以轻松地搜索到K了。

例如：

A -> B -> C -> D -> B K = 1000; S = A;

A - 0
B - 1
C - 2
D - 3
B - 1 (+ 4N)
在这里，您可以检查k - (1+4N) = 0的floor() > 1000 - 1 - 4N = 0 > 999 = 4N > N=249 => 最佳的B是249*4 + 1 = 997
更简单的方法是计算：round(k - offset, cycle)

从这里你只需要再数几步。
在这个例子中（作为REGEX）：A(BCD){249}BCD

- Tomer W