从源到目的地的步行次数
给定一个图和两个顶点 src 和 dest，计算从 src 到 dest 的路径总数，其中路径长度为 k(它们之间应该正好有 k 条边)。请注意，该图表示为邻接矩阵。 例如，考虑以下图表:
长度为 2 的从顶点 0 到顶点 3 的路径数为 2 ({0->1->3}和{0->2->3})。 我们已经在中讨论了 O(V 3 K)方法，计算从一个源到一个目的地的所有可能的步行，正好有 K 条边。本文讨论了一种 O(V 3 Log K)方法。
方法:想法是计算结果矩阵，其中结果=(图表) k 。长度为 k 的从源到目的地的路径总数将简单地为结果【src】【dest】。我们使用这个技术来计算给定图的邻接矩阵的幂。 这里指数= 7 所用的幂函数递归树如下:
下面是上述方法的实现:
Output:
Total number of walks: 2
时间复杂度:
版权属于：月萌API www.moonapi.com，转载请注明出处
