我对计算图中两个节点（稀疏、有向和包含循环）之间的简单路径总数（无节点重复）感兴趣。该图是一个强连通分量。
我最初尝试使用矩阵乘法，将邻接矩阵提高到从 2 到 n-1 的所有幂，n 是节点数。然而，由于图中的循环，这失败了。对于 DAG，只需计算所有这些权力并将它们总结起来就可以完成这项工作。
问问题
992 次
2 回答
1
不幸的是，这个问题在任意图上非常重要。有一种分析方法，但它需要显式计算，因此无法提供通用答案。它包括通过变量 x_node 对离开节点的每条边进行加权。然后考虑这些变量相互通勤并且平方为零。如此加权的邻接矩阵的幂生成简单路径。这个邻接矩阵被称为图的幂零邻接矩阵，变量存在于克利福德代数中（参见 R. Schott 的文献）。正如我之前提到的，不幸的是，这种方法在相当大的图上基本上没有用，因为它需要分析计算实际的矩阵幂。我希望在这一点上被证明是错误的。
于 2013-11-27T11:26:21.593 回答
1
这个问题没有有效的算法。
计算从顶点s到t的简单路径数量的问题是#P-complete。因此，您不能指望一个多项式时间算法可以通用。参见例如https://cstheory.stackexchange.com/q/20246/5038、https://stackoverflow.com/a/5570751/781723、https://cs.stackexchange.com/q/423/755 。 _ _ _
是时候尝试找到一些方法来避免解决这个问题，或者使用近似算法或其他东西。
于 2014-06-01T23:39:10.473 回答