图中两个给定节点之间给定长度的所有路径

Question

我遇到了这个问题:

http://www.iarcs.org.in/inoi/contests/oct2005/Advanced-2.php

问题基本上是图表.您将获得一个包含多达70个节点的图形,以及一个邻接矩阵,用于说明两个节点之间存在多少条边.每条边都是双向的.

现在的问题是问你找出的任意两个节点N1和N2之间的固定长度的N个不同路径的数量.路径可以重复.即,路径可以通过已包含的节点.

最天真的算法是运行广度优先搜索并检查Nth层中出现的N2数量,其中BFS树以N1为根.但这不会奏效.

怎么去呢？

Answer 1

这个问题的解决方案很简单 - 将邻接矩阵提高到N次幂,并且(N1, N2)每个对N1和N2 的答案将位于单元格中 - 基本图论.

您还可以使用矩阵的二进制求幂来更快地计算答案.

要理解为什么上述算法有效,请尝试写下求幂的前几个步骤.您会注意到,在每次迭代中,矩阵都会保持给定固定长度的路径从1到N.如果您记下执行矩阵多重时如何计算单元格,您还应该看到为什么会这样.

注意:对于如何计算长度达到固定长度的所有路径,还有一个非常酷的黑客 - 只需在起始顶点添加"循环",从而使其可以从自身访问.