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

Question

我遇到了这个问题：

问题基本上是关于图表的。您将获得一个最多包含 70 个节点的图和一个邻接矩阵，该矩阵告诉您两个节点之间存在多少条边。每条边都是双向的。

现在问题要求您找出任意两个节点 N1 和 N2 之间固定长度 N 的不同路径的数量。路径可以有重复。即，路径可以通过已经包含的节点。

最简单的算法是运行广度优先搜索并检查有多少 N2 出现在第 N 层，BFS 树以 N1 为根。但这行不通。

怎么办？

score 7 · Accepted Answer

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

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

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

注意：关于如何计算长度为固定长度的所有路径还有一个非常酷的 hack -只需在起始顶点添加一个“循环”，从而使其可以从自身访问。

1 回答 1