我有一个 n 部分（无向）图，作为邻接矩阵给出，例如这里的这个：
A B C D 一个 0 1 1 0 b 0 0 0 1 c 0 0 0 1 d 0 0 0 0
我想知道是否有一组矩阵运算可以应用于这个矩阵，这将导致一个矩阵“列出”这个图中的所有路径（长度为 n，即通过所有分区）。对于上面的示例，有路径 a->b->d 和 a->c->d。因此，我想得到以下矩阵作为结果：
A B C D 1 1 0 1 1 0 1 1
第一条路径包含节点 a、b、d，第二条路径包含节点 a、c、d。如有必要，结果矩阵可能有一些全为 0 的行，如下所示：
A B C D 1 1 0 1 0 0 0 0 1 0 1 1 0 0 0 0
谢谢！
PS我看过计算传递闭包的算法，但这些通常只告诉两个节点之间是否存在路径，而不是直接告诉哪些节点在该路径上。
您可以做的一件事是计算矩阵 A 的 n 次方。结果将告诉您从任何一个顶点到任何另一个顶点的长度为 n 的路径有多少。
现在，如果您有兴趣了解路径上的所有顶点，我不认为使用纯矩阵运算是要走的路。请记住，您有一个 n 部图，我将按如下方式设置数据结构：（请记住，除了小值之外，所有空间成本都是昂贵的。）
每一列将有我们图中每个节点的一个条目。如果该节点在从我们指定的起始顶点或起始集的第 n 次迭代中可到达，则第 n 列将包含 1，否则为零。每个列条目还将包含指向第 n-1 列中顶点的反向指针列表，这些顶点指向第 n 列中的该顶点。（这类似于维特比算法，只是我们必须为每个条目维护一个反向指针列表，而不仅仅是一个。）这样做的复杂性是 (m^2)*n，其中 m 是图，n 是所需路径的长度。
我对您的顶部矩阵有点困惑：对于无向图，我希望邻接矩阵是对称的。
不，没有纯矩阵方式来生成所有路径。请使用纯组合算法。
“你可以做的一件事是计算矩阵 A 的 n 次方。结果将告诉你从任何一个顶点到任何另一个顶点的长度为 n 的路径有多少。”
矩阵的力量产生的是步行而不是路径。