algorithm - 给定一个带有自循环的有向加权图，找到与给定节点 x 恰好 k 距离的节点列表？

Question

图中每条边的权重为 1，图中可能有环，如果一个节点有自环，它可以是从 0 到无穷大的任何距离，具体取决于编号。时间我们采取 self 循环。

我已经用bfs解决了这个问题，但是对距离的约束是10^9的量级，所以bfs很慢。

我们将被要求对表格的给定图进行多个查询(距离，来源)o/p 是从源顶点开始的给定距离处的节点列表。

约束

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

我有一种感觉，因为没有，所以会有很多重复的计算。节点很小，但我无法弄清楚如何在较小的问题中减少问题。

执行此操作的有效方法是什么？

编辑:我试过使用矩阵求幂，但对于给定的约束，它太慢了。该问题的时间限制为 1 秒。

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.

这意味着通过创建这个矩阵然后计算指数，您可以轻松得到答案。

对于快速指数计算，您可以使用 exponent by squaring ，这将产生 O(M(n)^log(k))其中 M(n)是cost for matrix multiplication对于 nXn 矩阵。

这也将为您在同一图表上查找不同查询时节省一些计算。

附录 - claim 证明:

基地:A^1 = A , 并且确实在 A根据定义，A[i][j]=1当且仅当 (V[i],V[j])在E

假设:假设声明对所有 l<k 都是正确的

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

让我们检查两个顶点 v1,v2带索引 i和 j .
如果有一条长度为k的路径在他们之间，让它成为v1->...->u->v2 .让索引u是m .
来自 i.h. 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) 是一条边，没有长度为 k-1 的路径来自 v至 u (否则 v1->..->u->v2 是一条长度为 k 的路径)。

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

QED

小提示:从技术上讲，A^k[i][j]是 i 之间的路径数和 j长度正好 k .这可以证明与上述类似，但更注重细节。
为了避免数字增长过快(这会增加 M(n) 因为您可能需要大整数来存储该值)，并且由于您不关心 0/1 以外的值 - 您可以将矩阵作为 bool 值 - 仅使用 0/1 值并修剪任何其他值。