给定长度的两个给定节点之间在曲线图的所有路径 [英] All paths of given length between two given nodes in a graph

问题描述

我碰到这个问题：

http://www.iarcs.org.in/ inoi /竞赛/ oct2005 /高级-2.PHP

这个问题主要是关于图形。你给出多达70个节点的图形，和一个邻接矩阵，它告诉如何在两个节点之间存在许多边缘。每个边缘是双向的。

The problem basically is about graphs. You are given a graph with up to 70 nodes, and an adjacency matrix which tells how many edges exist between two nodes. Each edge is bidirectional.

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

Now the question asks you to find out the number of distinct paths OF A FIXED LENGTH N between any two nodes N1 and N2. The path can have repetitions. I.e., the path can go through an already included node.

该naivest算法中是先运行一个广度搜索和检查N2多少出现在第N层的BFS树扎根在N1。但是，这不会工作。

The naivest algo is to run a breadth first search and check how many N2 appear in the Nth layer with the BFS tree rooted at N1. But this wont work.

如何去做？

推荐答案

解决这个问题很简单 - 提高邻接矩阵的N次方，答案将在小区坐（ N1，N2）对于每对N1和N2 - 。基本图论

The solution to this problem is simple - raise the adjacency matrix to the N-th power and the answer will sit in the cell (N1, N2) for each pair N1 and N2 - basic graph theory.

您还可以使用的基质二进制幂计算答案更快。

You can also make use of binary exponentiation of the matrix to compute the answer faster.

要了解的为什么做上述算法的工作，尽量记下前几步的幂。你会发现，在每次迭代矩阵保存与给定的固定长度从1去N.路径如果你写下来是怎么计算的单元格执行矩阵mutliplication你也应该看到，当它为什么会发生这样。

To understand why does the above algorithm work, try to write down the first few steps of the exponentiation. You will notice that on each iteration the matrix holds the paths with a given fixed length going from 1 to N. If you write down how is a cell computed when performing matrix mutliplication you should see also why does it happen so.

注：也有关于你如何计算长度的所有路径一个很酷的黑客至固定长度-simply在开始顶点添加一个循环，从而使得它本身的访问

NOTE: there is also a really cool hack on how do you compute all paths with length up to a fixed length -simply add a "loop" at the start vertex thus making it accessible from itself.

这篇关于给定长度的两个给定节点之间在曲线图的所有路径的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！