给定一个带有自循环的有向加权图,找到与给定节点 x 恰好 k 距离的节点列表?
Given a directed weighted graph with self loops ,find the list of nodes that are exactly k dist from a given node x?
图中每条边的权重都是1,图中可能有环,如果一个节点有自环,它可以是从0到无穷大的任意距离,具体取决于编号。时间我们采取自我循环。
我已经用bfs解决了这个问题,但是距离的限制是10^9,所以bfs很慢。
我们将被要求对表格的给定图表进行多次查询
(距离,来源)
o/p 是从源顶点开始的给定距离处的节点列表。
约束条件
1<=Nodes<=500
1<queries<=500
1<=distance<=10^9
我有一种感觉,因为这个号码会重复计算很多次。节点数很小,但我无法弄清楚如何在较小的问题中减少问题。
执行此操作的有效方法是什么?
编辑:我试过使用矩阵求幂,但对于给定的约束,它太慢了。该问题的时间限制为 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.
这意味着通过创建这个矩阵然后计算指数,您可以轻松得到答案。
对于快速指数计算,您可以对 nXn 矩阵使用 exponent by squaring, which will yield O(M(n)^log(k))
where M(n)
is the cost for matrix multiplication。
在同一图表上查找不同的查询时,这也将为您节省一些计算。
附录-索赔证明:
基础: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
当且仅当存在从 V[i]
到 V[j]
.
的长度为 k-1
的路径
让我们检查索引为 i
和 j
的两个顶点 v1,v2
。
如果它们之间有一条长度为 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) 是一条边,没有从 v
到长度 k-1
的路径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 以外的值 - 您可以将矩阵视为布尔值 - 仅使用 0/1 值并修剪其他任何值。
如果你的图中有循环,那么你可以推断出 cycle * N + 1
中每个相邻节点之间有一个 link,因为你可以根据需要进行迭代。
这让我想到了,我们可以利用循环来发挥我们的优势!
在检测循环时使用 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
> 1000 - 1 - 4N = 0
> 999 = 4N
> N=249
=> 最好的 B 是 249*4 + 1
= 997
更简单的方法是计算:round(k - offset, cycle)
从这里你只能再数几步了。
在此示例中(作为正则表达式):A(BCD){249}BCD
图中每条边的权重都是1,图中可能有环,如果一个节点有自环,它可以是从0到无穷大的任意距离,具体取决于编号。时间我们采取自我循环。
我已经用bfs解决了这个问题,但是距离的限制是10^9,所以bfs很慢。
我们将被要求对表格的给定图表进行多次查询 (距离,来源) o/p 是从源顶点开始的给定距离处的节点列表。
约束条件
1<=Nodes<=500
1<queries<=500
1<=distance<=10^9
我有一种感觉,因为这个号码会重复计算很多次。节点数很小,但我无法弄清楚如何在较小的问题中减少问题。
执行此操作的有效方法是什么?
编辑:我试过使用矩阵求幂,但对于给定的约束,它太慢了。该问题的时间限制为 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.
这意味着通过创建这个矩阵然后计算指数,您可以轻松得到答案。
对于快速指数计算,您可以对 nXn 矩阵使用 exponent by squaring, which will yield O(M(n)^log(k))
where M(n)
is the cost for matrix multiplication。
在同一图表上查找不同的查询时,这也将为您节省一些计算。
附录-索赔证明:
基础: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
当且仅当存在从 V[i]
到 V[j]
.
k-1
的路径
让我们检查索引为 i
和 j
的两个顶点 v1,v2
。
如果它们之间有一条长度为 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) 是一条边,没有从 v
到长度 k-1
的路径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 以外的值 - 您可以将矩阵视为布尔值 - 仅使用 0/1 值并修剪其他任何值。
如果你的图中有循环,那么你可以推断出 cycle * N + 1
中每个相邻节点之间有一个 link,因为你可以根据需要进行迭代。
这让我想到了,我们可以利用循环来发挥我们的优势!
在检测循环时使用 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
> 1000 - 1 - 4N = 0
> 999 = 4N
> N=249
=> 最好的 B 是 249*4 + 1
= 997
更简单的方法是计算:round(k - offset, cycle)
从这里你只能再数几步了。
在此示例中(作为正则表达式):A(BCD){249}BCD